Data Structures & Complexity — Notes

Interview heuristic

Before writing code, say out loud: "I'll use X because the dominant operation is Y, which is O(_) on X." That single sentence wins.

Practical numbers (worth memorising)

• Cache line: 64 B.
• DRAM access: ~100 ns.
• L1 access: ~1 ns. So a cache miss is ~100× slower.
• Branch mispredict: ~5 ns.
• Atomic CAS uncontended: ~20 ns. Contended: 100s of ns.

These numbers turn "Big-O" reasoning into latency reasoning when it matters.

When O(n²) is fine

• n ≤ 1000.
• All-pairs algorithms on small graphs.
• Anything one-shot, run offline.

When O(n log n) becomes O(n)

• Counting / radix / bucket sort when the universe is small.
• Top-k with a heap of size k: O(n log k), not O(n log n).

When O(log n) becomes O(1)

• Hash maps (with caveats).
• Bloom filters / count-min for probabilistic answers.

Refs

• "Introduction to Algorithms" — Cormen et al. (CLRS).
• "Algorithms" — Sedgewick & Wayne (book + Coursera).
• bigocheatsheet.com.
• "Numbers Everyone Should Know" (Jeff Dean, ~2010).