Practical Complexity Analysis

Big O in the real world

The textbook gives you O(n) vs O(n²), but production code is messier. Real systems have best, worst, and average cases; operations whose cost varies; and inputs that arrive in patterns. Practical analysis means knowing when the textbook answer is misleading.

Best, worst, and average case

Big O usually denotes worst case, but many algorithms behave better on typical input:

• Quicksort — O(n²) worst, O(n log n) average. With a random pivot, the worst case is astronomically unlikely.
• Hash map lookup — O(n) worst (all keys collide), O(1) average.
• Insertion sort — O(n²) worst, O(n) best (already-sorted input).

Always ask which case your analysis describes. Average case is often what users experience; worst case is what you must defend against in adversarial or pathological conditions.

Amortized analysis

Some operations are usually cheap but occasionally expensive. Amortized analysis spreads the expensive operation's cost across all the cheap ones, giving a true picture of long-run performance.

The classic example is a dynamic array (Python list, JS array, C++ vector):

arr.append(x);   // usually O(1)...
                 // but when the backing array is full,
                 // it allocates a bigger one and copies everything → O(n)

The copy is O(n), but it happens only after n appends. Spread the cost and each append is amortized O(1). The trick is that the array doubles in capacity each time, so the total copying work across all resizes is n + n/2 + n/4 + ... ≈ 2n.

Common gotchas

• Hidden loops — calling .indexOf() or .contains() inside a loop turns an O(n) algorithm into O(n²).
• String concatenation — repeated s += "x" is O(n²) in many languages because it copies the whole string each time; use a StringBuilder/join.
• Accidentally quadratic — nested loops over a hash map's keys where a single pass would do.

When Big O lies

For small n, constant factors dominate. An O(log n) binary search on a 10-element array can be slower than a O(n) linear scan, because the linear scan has better cache behavior and no branch mispredictions. This is why libraries switch strategies at small sizes — the asymptotic winner isn't always the practical one.

// A real hybrid: introspective sort
// - quicksort for large partitions (fast average case)
// - switch to insertion sort below ~16 elements (lower constants)
// - fall back to heapsort if recursion gets too deep (guards the worst case)

Measure, don't guess. Big O tells you how an algorithm scales; profiling tells you whether it is actually fast on your data. Optimize the one your measurements point at.