Ai cũng học Big-O rồi quên, vì nó nghe như toán hàn lâm. Nhưng Big-O là thứ ĐO được. Bài này chạy thật trong go-lab: khi N tăng gấp đôi, O(n) ×2, O(n²) ×4, còn O(log n) gần như đứng yên. Chính tỉ lệ 'nhân đôi N' đó là cách nhận ra độ phức tạp của code bạn — và lý do một hàm O(n²) chạy ngon lúc dev lại làm sập hệ thống lúc scale.
Binary search O(log n) nghe là biết thắng linear O(n). Bài này đo thật trong go-lab: ở N=262.144, binary nhanh hơn 1.125 lần một lần tìm. Nhưng binary đòi mảng đã sắp — và chi phí sort trước (306 µs) đổi cục diện: nếu chỉ tìm 1-2 lần trên mảng chưa sắp, linear thắng. Cộng thêm yếu tố cache khiến ở N nhỏ binary chỉ nhỉnh 3,7 lần.
O(n²) chậm hơn O(n log n) — ai cũng biết. Nhưng đo thật trong go-lab cho thấy nhiều thứ sách không nói: insertion sort O(n²) lại NHANH HƠN quicksort tự viết ở N=1.000; quicksort tự viết thua mergesort vì cấp phát bộ nhớ; và sort.Ints của thư viện chuẩn (introsort) đánh bại mọi bản tự viết. Cài đặt quan trọng ngang độ phức tạp.
Map/dict cho tra cứu O(1) — nhanh bất kể dữ liệu lớn cỡ nào. Bài này đo thật trong go-lab: hashtable và map Go giữ ~1-21 ns dù N tăng 256 lần, trong khi quét slice tăng tuyến tính tới 32 µs. Nhưng O(1) chỉ là trung bình: hàm băm tệ (mọi key về một bucket) làm tra cứu chậm gấp 11.874 lần, và quên pre-size map khiến chèn chậm gấp đôi vì rehash.
Cây BST hứa tra cứu O(log n), nhưng chèn dữ liệu đã sắp vào nó một cách ngây thơ thì cây suy biến thành danh sách liên kết O(n). Bài này đo thật trong go-lab: cùng N=64.000, BST cân bằng tra cứu 99 ns còn BST suy biến 29.618 ns — chậm gấp 300 lần. Map Go (hash) còn nhanh hơn cả cây cân bằng. Vậy khi nào mới nên dùng cây?
Cần 10 phần tử lớn nhất từ 8 triệu? Sắp xếp cả mảng rồi lấy 10 đầu là cách ai cũng nghĩ tới — và là cách sai. Bài này đo thật trong go-lab: min-heap size k lấy top-10 trong 4,3 ms, còn full sort mất hơn 1 giây — nhanh hơn 247 lần. Kèm cơ chế heap làm hàng đợi ưu tiên với Push/Pop O(log n), nền tảng của Dijkstra và lập lịch.