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.
f(n) = 3n + 5 is Theta(n): it is O(n), never more than a constant times n past some n0, and Omega(n), never less than a constant times n. The rows below f are the two references, 1 x n and 4 x n. Where f sits between them, both bounds hold.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
n = 1: f(n) = 8. Is it at most 4n = 4?
Answer: No, over it. Below n = 5 the extra 5 is bigger than the spare n.
n = 2: f(n) = 11. Is it at most 4n = 8?
Answer: No, over it. Below n = 5 the extra 5 is bigger than the spare n.
n = 3: f(n) = 14. Is it at most 4n = 12?
Answer: No, over it. Below n = 5 the extra 5 is bigger than the spare n.
n = 4: f(n) = 17. Is it at most 4n = 16?
Answer: No, over it. Below n = 5 the extra 5 is bigger than the spare n.
n = 5: f(n) = 20. Is it at most 4n = 20?
Answer: Yes, within the bound. 3n + 5 <= 4n once n >= 5.
n = 6: f(n) = 23. Is it at most 4n = 24?
Answer: Yes, within the bound. 3n + 5 <= 4n once n >= 5.
n = 7: f(n) = 26. Is it at most 4n = 28?
Answer: Yes, within the bound. 3n + 5 <= 4n once n >= 5.
n = 8: f(n) = 29. Is it at most 4n = 32?
Answer: Yes, within the bound. 3n + 5 <= 4n once n >= 5.
How it runs, step by step
f(n) = 3n + 5 is Theta(n): it is O(n), never more than a constant times n past some n0, and Omega(n), never less than a constant times n. The rows below f are the two references, 1 x n and 4 x n. Where f sits between them, both bounds hold.
Bounds table for f of n equals 3n plus 5 against n and 4n.
n = 1: f = 8, between n = 1 and 4n = 4? The lower bound holds, 8 >= 1. The upper bound fails, 8 > 4: the constant 5 still dominates. Big O only promises the bound for large n.
n 1: f 8, upper bound fails.
n = 2: f = 11, between n = 2 and 4n = 8? The lower bound holds, 11 >= 2. The upper bound fails, 11 > 8: the constant 5 still dominates. Big O only promises the bound for large n.
n 2: f 11, upper bound fails.
n = 3: f = 14, between n = 3 and 4n = 12? The lower bound holds, 14 >= 3. The upper bound fails, 14 > 12: the constant 5 still dominates. Big O only promises the bound for large n.
n 3: f 14, upper bound fails.
n = 4: f = 17, between n = 4 and 4n = 16? The lower bound holds, 17 >= 4. The upper bound fails, 17 > 16: the constant 5 still dominates. Big O only promises the bound for large n.
n 4: f 17, upper bound fails.
n = 5: f = 20, between n = 5 and 4n = 20? The lower bound holds, 20 >= 5. The upper bound holds too, 20 <= 20, for the first time: n0 = 5.
n 5: f 20, upper bound holds.
n = 6: f = 23, between n = 6 and 4n = 24? The lower bound holds, 23 >= 6. The upper bound holds too, 23 <= 24.
n 6: f 23, upper bound holds.
n = 7: f = 26, between n = 7 and 4n = 28? The lower bound holds, 26 >= 7. The upper bound holds too, 26 <= 28.
n 7: f 26, upper bound holds.
n = 8: f = 29, between n = 8 and 4n = 32? The lower bound holds, 29 >= 8. The upper bound holds too, 29 <= 32.
n 8: f 29, upper bound holds.
From n = 5 onward, n <= f(n) <= 4n, so f is Theta(n). The lower reference makes it Omega(n), the upper makes it O(n), and the small n where the bound fails do not matter: the definitions only speak about n beyond some n0.
f is Theta of n from n0 equals 5.
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