Complexity is a contract, not a fact

Every complexity statement you have ever read was a contract. "Hash map lookup is O(1)" is a contract with three clauses. "Dynamic array append is O(1) amortised" is a contract with different clauses. "Dijkstra is O((V+E) log V)" has its own. The problem is that most developers read complexity statements as if they were observations about the world, as if the running time were a property of the algorithm alone, rather than a joint property of the algorithm, the input distribution, and the hardware.

I've debugged enough production performance regressions to know what happens when the contract is violated. Nothing looks wrong. The code looks correct. The complexity on paper is fine. But the program is slow. The cause is usually one of three assumption failures, and naming them is worth a thousand profiler sessions.

Assumption 1. The input distribution

Quicksort is O(n log n) in expectation. It is O(n²) in the worst case. The difference depends entirely on the distribution of inputs. Over random inputs, quicksort's partition cuts the array in half on average; over already-sorted inputs with a naive pivot choice, partition cuts off one element at a time and the algorithm degenerates to bubble sort.

Production systems do not see random inputs. They see inputs correlated with yesterday's inputs, with the current hour, with the week of the month. If your data is already nearly sorted, which it almost always is, because most real-world data is derived from some ordering, a naive quicksort is slow. Randomised pivot selection or introsort (the hybrid used in C++'s std::sort) fix this; plain median-of-three pivot selection does not, if the adversary is "every time the user sorted yesterday".

The general pattern: an algorithm's claimed complexity assumes an input distribution. Find out what distribution it assumes. Then check whether your production inputs match.

Assumption 2. The cost of primitive operations

When CLRS writes "each operation costs a constant", it means "a constant with respect to n". It does not mean "a constant with respect to everything". Hashing a string of length L costs O(L), not O(1). Comparing two strings of length L costs O(L). So a hash-map lookup keyed on strings of length L is not O(1), it's O(L). For most applications L is small and constant, and the shorthand works. For applications where L is large or unbounded (URLs, log lines, tokenised search queries) the complexity statement silently lies.

The same failure afflicts Python code that uses arbitrary-precision integers. Python's int has no size limit, so multiplying two n-digit integers is O(n) in bit-length, or rather, O(n²) with schoolbook multiplication, O(n log n) with the Karatsuba-based algorithm Python actually uses. A Fibonacci computation that looks O(n) in iteration count is actually O(n²) in bit operations, because the numbers themselves grow. I have seen Jupyter notebooks that "worked fine up to n = 1000" run for hours at n = 10000, because the asymptotic was wrong in the only way that mattered.

The lesson: every "O(1)" that operates on a non-atomic value is a lie the field tells itself. Size-aware complexity is more honest.

Assumption 3. The memory model

Algorithmic complexity assumes uniform memory: every access costs the same. Real memory is a hierarchy. L1 cache hits are ~1 ns; L2 hits are ~4 ns; main memory hits are ~100 ns; disk is milliseconds. A "linear scan" of a billion-element array that fits in RAM is fast; the same scan of an array that pages to disk is three orders of magnitude slower, and the complexity analysis does not see the difference.

The practical consequence is that contiguous data beats pointer-chasing even when the asymptotic complexity is identical. A linear search over a vector can outperform a binary search over a linked list, because the linear search touches cache lines sequentially while the binary search jumps randomly through memory. Sedgewick's measurements on this are striking: for small-to-medium n, the "asymptotically worse" algorithm wins in wall-clock terms.

This is also why Python's list operations are often faster than the hash-based data structures "should" be in asymptotic terms. The cache effects favour contiguous storage, and the hash table's bucket layout spreads work across unpredictable cache lines. Asymptotic thinking alone will not predict which is faster.

Amortised versus worst-case

A fourth assumption worth naming separately: amortised complexity is an average, not a guarantee. list.append is amortised O(1) in Python, because occasional resizes cost O(n) but are rare enough to be absorbed. In steady-state throughput, this is fine. In real-time systems with hard latency budgets, it is not, one of those amortised resizes might be the one that misses your deadline.

Game engines, trading systems, and audio-processing code commonly refuse amortised data structures. They preallocate at the maximum expected size and reject inserts that would force a resize. The result is worst-case O(1), which is what the deadline actually requires. Most engineers never encounter this constraint, but when it bites, understanding that "amortised" and "worst-case" are different things is the whole game.

How to read complexity statements after reading this

When someone says "X is O(f(n))", ask:

1. Over what inputs? Worst case, average case, expected case over a specific distribution?
2. Counting what operations? Comparisons, memory accesses, bit operations, hash computations? The choice matters.
3. With what memory assumptions? Uniform RAM? Fits in L3? Out-of-core?
4. Amortised or worst-case? And, if amortised, can the worst-case single operation hurt you?

Applied to a real example: "Python dict lookup is O(1)" expands to "O(1) amortised expected, over non-adversarial keys, assuming the keys are atomic or have bounded hash cost, with uniform memory access costs, under hash-table load factors that are periodically bounded by resizing". That is the full contract. When you use a dict keyed on long strings in a tight loop inside a real-time system, multiple clauses of that contract are under stress at once.

Practical advice

Three habits make a large difference:

• Name the assumption explicitly when you state a complexity. "O(n) expected, over uniformly distributed keys, with bounded hash cost" is more useful than "O(n)" in a code review, it flags what will go wrong when the assumption fails.
• Profile on production-shaped inputs. Synthetic benchmarks violate assumption 1 almost always. Use real logs, real URLs, real user behaviour.
• Prefer simple cache-friendly code over "asymptotically better" alternatives for small n. The crossover point for "better" is often larger than your n.

Closing thought

Complexity notation is one of the greatest intellectual achievements in computer science. It lets us reason about algorithms without knowing anything about the machine they'll run on. That abstraction is the source of its power and, in production, of its hazards. Use it as a contract, not as a promise. Read the clauses.

If you want the mechanics of amortised analysis in detail, the relevant section on dynamic arrays covers the doubling-strategy proof, and the hash-maps module discusses amortised O(1) operations and when they degrade.