Giữ nhiều phiên bản của một cấu trúc thì phải copy cả nó mỗi lần sửa, tốn O(n)? Đo ra: một persistent vector kiểu trie nhánh 32 chỉ copy đường dẫn tới phần đổi — update nhanh hơn copy cả mảng 319 lần, và mỗi phiên bản mới tốn 1,76 KB thay vì 4 MB, ít hơn 2345 lần. Còn đọc thì chỉ chậm hơn mảng phẳng 1,1 lần vì nhánh rộng giữ cây nông.
Lock-free không dùng khóa nên luôn nhanh hơn mutex? Đo ra: với ít luồng thì atomic nhanh hơn hẳn (1 luồng mutex 4,1 ns vs atomic 1,6 ns), nhưng 8 luồng tranh gay gắt một biến thì atomic fetch_add chỉ ngang mutex (20,8 vs 22,1 ns) và CAS-loop tự viết tệ hơn mutex 6,8 lần (141,5 ns) vì thử lại liên tục. Và mutex không tranh chỉ tốn vài ns.
Hash map O(1) nên luôn nhanh nhất cho tra cứu? Đo ra: với khóa chuỗi (băm phải đọc cả 24 ký tự ~10ns), quét tuyến tính một mảng nhỏ thắng hash map tới n≈16 — vì hằng số nhỏ hơn nhiều: cache liền, so sánh thoát sớm, không băm, không con trỏ. Big-O là tiệm cận n→vô cùng; ở n nhỏ chính hằng số quyết định, và điểm giao tùy giá của khóa.
Cứ đo thời gian là biết ngay độ phức tạp? Đo ra: ở n nhỏ hằng số và overhead lấn át nên tỉ số T(2n)/T(n) lung tung (1,0/4,0/1,75), và cache tạo gãy khúc — truy cập ngẫu nhiên nhảy từ 0,9ns (L1) lên 96ns (RAM), khiến vòng O(n) trông siêu tuyến tính. Nhưng đo đúng cách thì tỉ số hội tụ chính xác: O(n)→2,00, O(n log n)→2,07.
Có một cấu trúc dữ liệu tốt nhất, cứ dùng nó cho mọi thứ? Đo ra: trên cùng 100.000 phần tử, cấu trúc thắng đảo hoàn toàn theo mẫu truy cập — đọc/tra cứu thì hash map thắng (31 lần binary search), duyệt tuần tự thì mảng phẳng thắng (8–9 lần), chèn/xóa ở giữa thì linked list thắng (731 lần). Không có cấu trúc tốt nhất chung; mẫu truy cập quyết định.
Chạy một lần bấm giờ là biết cấu trúc nào nhanh hơn? Đo ra bốn cái bẫy: lần chạy đầu chậm 1,5 lần (cache lạnh, page fault); nếu quên volatile SINK thì -O2 xóa sạch vòng lặp và đo ra 0 ns (số bịa); đo một thao tác đơn cho 84 ns rác (toàn overhead đồng hồ) so với 0,23 ns thật; và nhiễu OS chỉ làm chậm nên phải lấy min, không lấy trung bình.