AlgoScope

Complexity in Numbers

algorithmbeginnerTime O(1) to O(2^n), by rowSpace O(1) to O(n), by row

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.

12481632insmrgqckfib

Extra memory beyond the input, in words, for insertion sort, merge sort, quick sort and recursive fib(n). Temporary arrays count, and so does the call stack: every open frame is memory.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.

  1. n = 2: how many extra words does merge sort need (temp array plus stack)?

    • 1
    • 2
    • 3

    Answer: 3. n for the temporary array plus log n frames: 3.

  2. n = 4: how many extra words does merge sort need (temp array plus stack)?

    • 1
    • 4
    • 6

    Answer: 6. n for the temporary array plus log n frames: 6.

  3. n = 8: how many extra words does merge sort need (temp array plus stack)?

    • 1
    • 8
    • 11

    Answer: 11. n for the temporary array plus log n frames: 11.

  4. n = 16: how many extra words does merge sort need (temp array plus stack)?

    • 1
    • 16
    • 20

    Answer: 20. n for the temporary array plus log n frames: 20.

  5. n = 32: how many extra words does merge sort need (temp array plus stack)?

    • 1
    • 32
    • 37

    Answer: 37. n for the temporary array plus log n frames: 37.

How it runs, step by step

  1. Extra memory beyond the input, in words, for insertion sort, merge sort, quick sort and recursive fib(n). Temporary arrays count, and so does the call stack: every open frame is memory.

    Extra memory table for four algorithms.

  2. n = 1. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 1 plus 0 frames of recursion: 1. Quick sort partitions in place and only keeps about 1 frames. Recursive fib holds 1 frames at its deepest.

    n 1: 1, 1, 1, 1 words.

  3. n = 2. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 2 plus 1 frames of recursion: 3. Quick sort partitions in place and only keeps about 2 frames. Recursive fib holds 2 frames at its deepest.

    n 2: 1, 3, 2, 2 words.

  4. n = 4. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 4 plus 2 frames of recursion: 6. Quick sort partitions in place and only keeps about 3 frames. Recursive fib holds 4 frames at its deepest.

    n 4: 1, 6, 3, 4 words.

  5. n = 8. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 8 plus 3 frames of recursion: 11. Quick sort partitions in place and only keeps about 4 frames. Recursive fib holds 8 frames at its deepest.

    n 8: 1, 11, 4, 8 words.

  6. n = 16. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 16 plus 4 frames of recursion: 20. Quick sort partitions in place and only keeps about 5 frames. Recursive fib holds 16 frames at its deepest.

    n 16: 1, 20, 5, 16 words.

  7. n = 32. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 32 plus 5 frames of recursion: 37. Quick sort partitions in place and only keeps about 6 frames. Recursive fib holds 32 frames at its deepest.

    n 32: 1, 37, 6, 32 words.

  8. Insertion sort is in place, O(1) auxiliary space. Quick sort is O(log n) from its stack alone. Merge sort pays O(n) for its buffer, and plain recursion such as fib pays O(n) in frames, which is space just as real as an array.

    Auxiliary space: constant, logarithmic, linear.

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

Related

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

Next up