Big-O as an Engineering Tool

Big-O isn't about being clever — it's about asking the right question before you write code: "how does this behave as the input grows?" A function that's fine at 100 items and unusable at 100,000 is a bug you shipped with confidence.

The rates that matter

• O(1) — hash map lookup, array index, append. The ideal.
• O(log n) — binary search, balanced tree ops. Doubling the input adds one step.
• O(n) — a single pass. Fine until it isn't — 100M rows is a minute of CPU.
• O(n log n) — a good sort. Rarely the bottleneck.
• O(n²) — nested loop over the same data. Fine at n=100, fatal at n=10,000.
• O(2^n) — exponential recursion without memoization. Fatal at n=30.

What to actually check

The loop-in-loop is the flag: for x in items: for y in items: compare(x, y) is O(n²) — it passes the test with 10 items and falls over at 10,000. A hash map turns the inner loop into O(1) lookup — the algorithm didn't get smarter, the data structure did.

Time vs space

Trading memory for speed is usually right — a cache, an index, a precomputed table. The reverse (using more time to save memory) is rare and usually means the algorithm is wrong.

Field notes

• Amortized analysis: append on a dynamic array is O(1) on average — the occasional O(n) resize is amortized over cheap appends. Don't count the worst case when it's rare.
• The constant factors matter at small scale — a "better" O(n log n) algorithm with a huge constant can lose to O(n²) at n<1000. Profile before optimizing.
• The question "what if this list has a million items?" is the code review question that catches half of performance bugs.