Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Complexity Claims: The Fine Print Behind Big-O

Overview

Big-O statements are theorems about an abstract machine, and the fine print is the machine. “O(1) array access”, “O(1) expected hash lookup”, “sorting cannot beat O(n log n)”, “O(log n) recursion depth” — each is true under specific assumptions about the cost of memory access, the behavior of hash functions, the allowed operations, and the resources available. Real machines violate those assumptions routinely, and the violations are not edge cases; they are the difference between a benchmark that predicts production and one that does not.

This chapter audits the five most consequential complexity claims. The counterexamples are all reproducible on commodity hardware — several of them are standard first-week exercises in performance engineering, which is precisely why they make good interview material: anyone can quote the asymptotics, and the candidate worth hiring can say when the asymptotics stop describing reality.

Assumption 1: “Array Access Is O(1) — and All O(1) Accesses Are Equal”

The taught rule

The RAM model charges one unit for any memory access, so a[i] is O(1) and an array is as fast at element 0 as at element n-1.

The hidden assumptions

  • The access hits the cache. A cache miss costs on the order of 100 nanoseconds — roughly 100–400 CPU cycles — versus a handful of cycles for L1.
  • The translation is cached. A TLB miss adds tens-to-hundreds of cycles; if the page is not mapped, the first touch is a page fault costing microseconds, plus the kernel’s zeroing of a fresh anonymous page.
  • All memory is equidistant. On NUMA machines, remote-node memory costs substantially more than local memory.
  • Contiguity is free. Accessing a linked list’s “next” pointer is also “O(1)” in the RAM model, but each hop risks its own cache miss.

Counterexample

Traverse a 10,000 × 10,000 matrix of 8-byte doubles (800 MB, far beyond cache). Row-major (a[i][j] inner loop over j) reads sequentially and touches a new 64-byte cache line every 8 elements; column-major (inner loop over i) strides 80,000 bytes, touching a new cache line — and a new 4 KB page — for every element. Both are Θ(n²) in the model; on real hardware the column-major version runs many times slower (commonly an order of magnitude), because the model’s “one unit per access” hides 64x differences in bytes transferred per useful element and page-fault behavior on first touch.

What changes when the assumption is removed

The corrected statement: array access is O(1) in operations and O(1) in cost only when the access is cache-resident; the honest complexity measure for large data is cache misses or block transfers, which depend on access pattern, not just element count. This is why sequential scans beat random scans on equal element counts, why loop interchange is a compiler optimization, and why “prefetch-friendly” layout is a design goal. The memory hardware chapter and the TLB deep dive cover the machinery.

Consequences

Interviews probe this with the row/column traversal question, with “why is iterating a linked list slower than an array despite the same big-O?”, and with “what does O(1) mean for a 100 GB array?” — the last one expecting “nothing, once you leave RAM”.

Assumption 2: “Hash Tables Are O(1) — Hash Functions Are Fine”

The taught rule

Hash table operations are O(1) expected, under the (simple) uniform hashing assumption: keys distribute independently and uniformly across buckets.

The hidden assumptions

  • The hash function actually distributes your keys uniformly. For string keys, a weak function (sum of bytes, modulo table size) is trivially predictable.
  • The keys are not chosen by an adversary. An attacker who knows the function can manufacture collisions — millions of keys that land in one bucket — turning every operation into O(n) and the whole table into a denial-of-service amplifier.
  • The load factor stays bounded, so resizing happens; adversarial or pathological workloads can force repeated resizing too.

Counterexample

In 2011, Klink and Wälde demonstrated the hash-flooding attack at the Chaos Communication Congress and coordinated disclosure followed via oCERT (advisory oCERT-2011-003): crafted POST parameters with colliding keys forced quadratic CPU behavior in parsers across PHP, Java, Python, Ruby, and others — a single crafted request could pin a core. The industry response was to make hash functions unpredictable: Python adopted SipHash with a per-process random key (PEP 456, Python 3.4), and Rust’s standard HashMap uses SipHash by default. The attack did not break the “O(1) expected” theorem; it broke the uniform-hashing premise for attacker-chosen keys.

What changes when the assumption is removed

The corrected statement: hash tables are O(1) expected under uniform or universal hashing; against adversaries, the guarantee requires a keyed or randomized hash (SipHash, universal families) — or a different structure (balanced trees, sorted arrays) with worst-case logs. The adversarial-input angle is developed in input constraints, and the misconception version (“hash lookup is always O(1)”) lives in the misconceptions project.

Consequences

The interview escalation is exactly “is a hash lookup O(1)? — what assumption gives you that? — how do you defend it against attackers?” — three questions that test whether the candidate knows the theorem’s premise, not just its conclusion.

Assumption 3: “Sorting Cannot Beat O(n log n)”

The taught rule

Comparison sorting has an Ω(n log n) lower bound, so merge sort, heapsort, and quicksort are optimal.

The hidden assumptions

  • The comparison model: the algorithm learns about elements only by comparing pairs. Each comparison has two outcomes, so a decision tree must distinguish n! permutations and its height is at least log2(n!) = Θ(n log n).
  • Nothing else is known about the keys. Integers from a small range carry information that comparisons throw away.

Counterexample

Sort 10^8 integers known to lie in [0, 10^6]. Counting sort allocates a 10^6-element tally array and makes one counting pass plus one output pass: O(n + k) — about 10^8 + 10^6 operations, no comparisons between elements, no Ω(n log n) wall. Radix sort generalizes this to wider keys by sorting digit-by-digit: O(d(n + k)). Both are decades old, standard, and proof that the lower bound is a property of the model, not of sorting.

What changes when the assumption is removed

The corrected statement: comparison-based sorting requires Ω(n log n) comparisons; when keys are integers (or otherwise structured), non-comparison sorts run in O(n + k) or O(d(n + k)); and when input is partially ordered, adaptive sorts exploit that too. There is a third escape hatch worth knowing: Timsort’s galloping mode exploits existing runs, so nearly-sorted inputs sort in close to linear time — also a model relaxation (the input is not a random permutation).

Consequences

The interview probe is “can we beat n log n?” and the strong answer distinguishes the model from the task. It pairs naturally with the misconceptions project’s treatment of average-case claims.

Assumption 4: “The Recursion Depth Is O(log n) — Or at Least Fine”

The taught rule

Divide-and-conquer halves the problem, so recursion depth is logarithmic and stack space is a non-issue.

The hidden assumptions

  • The problem actually halves. Quicksort with a fixed pivot on already-sorted input partitions 1/(n-1) every time: depth Θ(n), not Θ(log n).
  • The stack can hold the depth. Default stacks are finite — 8 MB on a typical Linux main thread, 1 MB on Windows, roughly 1000 interpreter frames in default CPython.
  • “Depth” and “work” are reported separately. An O(n log n)-work algorithm can be O(n)-deep, and O(n)-work ones (recursive list summation, recursive DFS on a path graph) can be O(n)-deep too.

Counterexample

Naive quicksort (first-element pivot) on 10^7 sorted integers: recursion depth 10^7. At even 100 bytes per frame that demands a gigabyte of stack — a segfault arrives long before, since 8 MB accommodates roughly 10^5 frames. Same input, same asymptotic work, but the space claim fails. This is exactly why production quicksorts recurse into the smaller partition and loop on the larger one, capping depth at log2 n ≈ 23 for 10^7 elements.

What changes when the assumption is removed

The corrected statement: state stack depth alongside time and heap space — worst-case depth is a separate resource; bound it explicitly (recurse on the smaller side, convert linear recursion to iteration, or run on an explicit heap-allocated stack), and remember that interpreted runtimes impose their own limits below the OS’s.

Consequences

“Your recursive DFS — what’s the stack depth on a 10^6-node path graph?” is a favorite probe because it separates candidates who memorized “DFS is O(V + E)” from those who track all resources.

Assumption 5: “Better Big-O Wins”

The taught rule

If algorithm A is asymptotically better than B, use A. Constants do not matter at scale.

The hidden assumptions

  • Constants are small relative to n. For small n they dominate entirely.
  • The asymptotically better algorithm’s constants and memory behavior are not pathological. Random access patterns, poor locality, and per-element overhead can erase an entire asymptotic class for realistic n.
  • The cost model matches the hardware. On disk, the number of block transfers dominates, not the number of comparisons.

Counterexample A: insertion sort beats quicksort for small n

For n below a few dozen, insertion sort’s tight inner loop, zero allocation, and perfect branch predictability beat quicksort’s recursion and partitioning overhead — measurably, on every mainstream platform. The standard libraries encode this: CPython’s Timsort and Java’s TimSort run binary insertion sort on short runs (minrun sized between 32 and 64), and OpenJDK’s primitive dual-pivot quicksort switches to insertion sort below 47 elements. “Slower algorithm wins” is not a paradox; it is the RAM model admitting it ignored constants.

Counterexample B: B-trees beat binary search on disk

Binary search over a sorted 10^9-record file performs ~log2(10^9) ≈ 30 comparisons — each potentially a random block read. On a spinning disk at ~10 ms per seek that is ~300 ms per lookup. A B-tree sized to the block (hundreds of keys per node) needs only log_B(10^9) ≈ 3–4 block reads — ~40 ms. Both are “O(log n)”; the base of the logarithm, invisible in big-O, is the entire difference. This is the external-memory model at work, and it is why databases use B-trees (see the repo’s B-tree chapter and the external-memory chapter) — while in-RAM the plain sorted-array binary search often wins on constants, which is the mirror-image lesson.

What changes when the assumption is removed

The corrected statement: choose by measured cost at your actual n and your actual hardware; big-O is a growth-rate contract for large n, not a winner-selection rule. Small n: simplest algorithm with the best constants. Disk-bound: minimize block transfers (B-trees, sequential scans). RAM-bound with huge n: asymptotics dominate and the constants decide between near-ties.

Consequences

This assumption is the bridge to the performance engineering track: benchmarks exist precisely because big-O cannot answer “which is faster here?”. In interviews, “when would insertion sort beat quicksort?” and “why does Postgres use B-trees rather than binary search?” are the canonical checks.

Interview Questions

  1. Both loops are Θ(n²). Why can one be 10x slower? Memory behavior is invisible to big-O: row-major traversal streams cache lines sequentially; column-major strides across pages, paying a cache miss (often a TLB miss or page fault) per element. Big-O counts accesses; hardware charges misses.
  2. What exactly does the Ω(n log n) sorting lower bound assume, and how do you beat it? The comparison model — only pairwise comparisons, two outcomes each, hence a decision tree of height log2(n!). Counting/radix sort exploit integer structure and run in O(n + k)/O(d(n + k)); adaptive sorts exploit presortedness. The bound is a model statement, not a sorting statement.
  3. A hash table is O(1) expected. Against an attacker? The expectation is conditional on (simple) uniform hashing, which attacker-chosen keys can violate — the 2011 hash-flooding disclosure (oCERT-2011-003) degraded parsers across many languages to O(n) per operation. Defenses: keyed/randomized hashing (SipHash), collision-count limits, or worst-case-log structures.
  4. Why does OpenJDK’s quicksort call insertion sort for fewer than 47 elements, and why does Timsort use binary insertion for short runs? Below small thresholds, constants and locality dominate asymptotics: insertion sort has no recursion, no partitioning, and excellent branch behavior. The thresholds are measured engineering facts, the standing rebuttal to “better big-O always wins”.
  5. Binary search and B-tree search are both O(log n). Why do databases use B-trees? The cost model on disk counts block transfers: binary search does ~log2(n) random reads; a B-tree with block-sized nodes does ~log_B(n), e.g. ~4 reads instead of ~30 for 10^9 records. The base of the logarithm — meaningless in big-O — is the whole design.

Key Takeaways

  • Big-O is a theorem about a model; before applying it, check which model — RAM, external-memory, comparison, uniform-hashing — the claim actually lives in.
  • Cache misses, TLB misses, and page faults make “O(1) memory access” the most routinely violated assumption in the book; access pattern matters as much as access count.
  • Adversarial inputs break average-case expectations (hash flooding, quicksort killers); randomness and keyed hashing are the standard repairs.
  • Stack depth is a separate resource from time and heap; worst-case depth Θ(n) is a real failure mode for Θ(n log n) algorithms.
  • Constants, thresholds, and logarithm bases are invisible to big-O and decisive in production — which is why measured benchmarks, not asymptotics, select implementations.

Cross-References