Complexity in Numbers
Big O is not about how long one run takes; it is about what happens to the count when the input doubles. Put sizes along the columns and functions along the rows and the growth classes separate themselves within a few doublings. The same table shows what a bound means: f(n) = 3n + 5 sits between n and 4n from some point on, so it is Theta(n) even though the constant wins for tiny n. It shows why one algorithm has three costs, why memory counts stack frames as well as arrays, and why a dynamic array's occasional expensive append averages out to a constant. The potential method makes the amortized argument exact: pick a potential function that measures saved-up credit, charge each operation its real cost plus the change in potential, and the cheap operations pay in advance for the expensive one, so every append costs the same amortized amount.
A dynamic array starts with capacity 1 and doubles whenever it is full. Most appends cost 1 write; an append that hits the limit also copies every element into the new array. The rows track each append's cost, the running total and the average so far.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.
Append 1 with 0 stored and capacity 1. What does it cost?
Answer: 1. Not full, so just the write.
Append 2 with 1 stored and capacity 1. What does it cost?
Answer: 2. Full, so every element is copied once: 1 + 1.
Append 3 with 2 stored and capacity 2. What does it cost?
Answer: 3. Full, so every element is copied once: 1 + 2.
Append 4 with 3 stored and capacity 4. What does it cost?
Answer: 1. Not full, so just the write.
Append 5 with 4 stored and capacity 4. What does it cost?
Answer: 5. Full, so every element is copied once: 1 + 4.
Append 6 with 5 stored and capacity 8. What does it cost?
Answer: 1. Not full, so just the write.
Append 7 with 6 stored and capacity 8. What does it cost?
Answer: 1. Not full, so just the write.
Append 8 with 7 stored and capacity 8. What does it cost?
Answer: 1. Not full, so just the write.
Append 9 with 8 stored and capacity 8. What does it cost?
Answer: 9. Full, so every element is copied once: 1 + 8.
Append 10 with 9 stored and capacity 16. What does it cost?
Answer: 1. Not full, so just the write.
Append 11 with 10 stored and capacity 16. What does it cost?
Answer: 1. Not full, so just the write.
Append 12 with 11 stored and capacity 16. What does it cost?
Answer: 1. Not full, so just the write.
How it runs, step by step
A dynamic array starts with capacity 1 and doubles whenever it is full. Most appends cost 1 write; an append that hits the limit also copies every element into the new array. The rows track each append's cost, the running total and the average so far.
Amortized cost of twelve appends to a doubling array.
Append 1: room for it, one write. Cost 1, total 1, average 1.0.
Append 1 costs 1, average 1.0.
Append 2: the array holds 1 and is full, so it grows to 2 and copies 1 elements. Cost 2, total 3, average 1.5.
Append 2 costs 2, average 1.5.
Append 3: the array holds 2 and is full, so it grows to 4 and copies 2 elements. Cost 3, total 6, average 2.0.
Append 3 costs 3, average 2.0.
Append 4: room for it, one write. Cost 1, total 7, average 1.7.
Append 4 costs 1, average 1.7.
Append 5: the array holds 4 and is full, so it grows to 8 and copies 4 elements. Cost 5, total 12, average 2.4.
Append 5 costs 5, average 2.4.
Append 6: room for it, one write. Cost 1, total 13, average 2.1.
Append 6 costs 1, average 2.1.
Append 7: room for it, one write. Cost 1, total 14, average 2.0.
Append 7 costs 1, average 2.0.
Append 8: room for it, one write. Cost 1, total 15, average 1.8.
Append 8 costs 1, average 1.8.
Append 9: the array holds 8 and is full, so it grows to 16 and copies 8 elements. Cost 9, total 24, average 2.6.
Append 9 costs 9, average 2.6.
Append 10: room for it, one write. Cost 1, total 25, average 2.5.
Append 10 costs 1, average 2.5.
Append 11: room for it, one write. Cost 1, total 26, average 2.3.
Append 11 costs 1, average 2.3.
Append 12: room for it, one write. Cost 1, total 27, average 2.2.
Append 12 costs 1, average 2.2.
Twelve appends cost 27 in total, under 3 per append, and the average keeps falling between resizes. Each element is copied at most once per doubling and the doublings shrink geometrically, so n appends cost at most about 3n: amortized O(1) each.
Total 27 for twelve appends: amortized constant.
Remember
- Big O describes how the count scales as n doubles: +1 for log n, x2 for n, x4 for n squared, squared for 2^n.
- O is an upper bound, Omega a lower bound, Theta both; all three only speak about n beyond some n0.
- Amortized cost is the total over a sequence divided by its length: rare expensive steps can still average O(1).
Topics covered
What the words mean
- Time Complexity
- Operation count as a function of input size; the classes separate within a few doublings of n.
- Auxiliary Space
- Extra memory beyond the input itself, such as merge sort's buffer or a recursion's frames.
- Big Theta
- A tight bound; the function stays between two scaled copies of the reference from some n0 on.
- In-place
- O(1) auxiliary space; the input is rearranged within itself.
- Accounting Method
- Each cheap append deposits credit that a later resize spends, so the average stays O(1).
- Aggregate Method
- Total cost of n operations divided by n.
Where this is used
DatabasesThe PostgreSQL query planner
The planner estimates row counts and multiplies them by tunable constants such as seq_page_cost, random_page_cost and cpu_tuple_cost, then picks the cheapest plan. A sequential scan is O(n) and an index scan is roughly O(log n) plus a random read per matching row, yet on a small table the planner still chooses the scan because below the crossover the constants decide, not the exponent. EXPLAIN ANALYZE prints the estimate next to the real count, so you can watch the n0 of the lesson in a live system.
SecurityHash flooding attacks
A hash table is O(1) on average and O(n) per lookup when every key lands in one bucket. In 2011 researchers showed you could choose POST parameter names that all collide under the string hash used by PHP, Java, Python and Ruby, turning a few hundred kilobytes of form data into quadratic work and taking the server down. The fix was not a faster hash but a randomly seeded one, which is why hash randomisation is on by default in Python from 3.3 onward: worst case matters when an adversary gets to pick the input.
Language runtimesHow append stays cheap in Go, Java and Python
Go slices, Java's ArrayList and CPython's list all grow by a multiplicative factor rather than a fixed number of slots. Any factor above 1 makes the total copying geometric, and with doubling it is n/2 + n/4 + ... < n across all growths, so each append is amortized O(1); growing by a constant 10 slots would copy on the order of n^2/20 elements over n appends and quietly make list building quadratic. This is exactly the argument the potential function makes precise, and it is why the documented cost is 'amortized constant' and not 'constant'.
OperationsThe Cloudflare outage of 2 July 2019
One new firewall rule contained a regular expression whose critical part was .*.*=.*, two greedy wildcards in a row before a literal. A backtracking engine tries every way those wildcards can split the input, so the step count grows super-linearly with line length: Cloudflare measured 23 steps to match x=x and 555 to match x= followed by twenty x's. CPU hit nearly 100 percent on every core serving HTTP across the network and the outage ran 27 minutes. Engines that compile to an automaton instead, such as RE2 and Go's regexp package, are linear in the input length and cannot be pushed into that case at all.
Why it works this way
An upper bound and a worst case are two different axes
O, Omega and Theta describe a function; best, worst and average describe which input produced it. Each case is its own function with its own three bounds. Quicksort's worst case is Theta(n^2) and its average is Theta(n log n), and both are true at once because they are statements about two different functions. Saying 'quicksort is O(n log n)' without naming the case is the sentence that hides the n^2.
Why the base of the logarithm is never written
Changing base only multiplies by a constant, since log2 n = log10 n / log10 2, and Big O absorbs constant factors, so O(log n) needs no base. The base does not disappear in practice though: it is the branching factor. A binary tree over a billion keys is about 30 levels deep and a B-tree with fanout 100 is about 5, and when each level costs a disk read that constant is the entire cost. Same complexity class, very different machine.
Amortized is not average case, and it will not fix your tail latency
Average case averages over a distribution of inputs, so an unlucky input beats it; amortized is a worst-case guarantee over a sequence with no probability in it at all. The expensive append in a dynamic array is not unlikely, it is certain, it simply cannot happen often enough to change the total. That distinction bites when a single call's latency is what you measure: the resize that copies a million elements still stalls that one append, so amortized O(1) and a bad p99 coexist happily, which is why real-time systems preallocate or grow incrementally instead.
The master theorem has gaps you can fall into
Cases 1 and 3 need f(n) to be smaller or larger than n^(log_b a) by a polynomial factor, not by a little. T(n) = 2T(n/2) + n / log n lands in the gap, since f is below n by only a log factor, and no case applies; you fall back to a recursion tree or Akra-Bazzi. Case 3 also carries a regularity condition, a * f(n/b) <= c * f(n) for some c < 1, which is easy to forget. The theorem also assumes every subproblem is the same size, so it says nothing about T(n) = T(n/3) + T(2n/3) + n.
Read more
- Big O notationWikipedia
- Master theorem (analysis of algorithms)Wikipedia
- Amortized analysisWikipedia
- Potential methodWikipedia
- Details of the Cloudflare outage on July 2, 2019Cloudflare