Algorithms

Data structures, the guide before this one, taught what to keep things in — the array, the hash table, the tree, the heap — and priced each one by hand. This guide is about what you do with them: how to price an algorithm before you run it, why the one that wins on paper can lose on the machine, and, at the end, how to look at a problem you have never seen and know which pattern it wants. It is the second of three, and it assumes the first — the growth shapes, the memory hierarchy, and every structure it built are used here without rebuilding them, with a pointer back when it matters. Everything is Python 3.11, and every number was measured on the machine these words were written on.

Worst, average, and amortised are three different questions

Here is one line of code:

record = cache[key]

It is a dict lookup, the thing every complexity table prices at O(1). Watch it cost O(1) and O(n) without a character changing — the only difference is the keys you filled the dict with. On the left, ordinary integer keys, whose hashes spread across the table. On the right, keys with a hand-written __hash__ that buckets them all onto the same value, the kind of hash someone writes when they key a cache by an object and forget how many objects share a shard:

       n     spread ns    collide ns   worst/avg
    1000          29.3       19697.6       673x
    2000          28.9       39723.5      1374x
    4000          29.7       80111.2      2697x
    8000          28.7      159591.0      5555x

The left column is flat. Ten times the keys, the same twenty-nine nanoseconds — that is O(1), the lookup computing a slot and going straight there. The right column doubles every time n doubles — 20,000, 40,000, 80,000, 160,000 — because when every key hashes alike the lookup has to walk the whole pile of collisions to find the one it wants. That is O(n), on the same line of code. (Why the spread keys stay flat and why the collision degrades linearly is the dict chapter of Data structures; here the point is only that they do.)

So "how much does cache[key] cost" has no single answer. It has three, and they are not three sizes of the same answer — they are answers to three different questions.

The guarantee, the bet, and the run

The worst case answers what is the most this can ever cost me? For the lookup it is O(n), that collision pile. It is the pessimist's number, and it is the right number whenever a single slow operation is a real problem — a request that must return inside a deadline, a control loop that cannot stall. You design a latency budget against the worst case because the worst case is the thing that blows the budget.

The average case answers what will it cost me typically? — and the word hiding in "typically" is the whole subject. Typically over what? An average is taken over some distribution of inputs, and the number is only as good as the distribution you assumed. The dict's famous O(1) is an average, and its fine print is assuming your keys' hashes spread out. The right-hand column above is that assumption being false. The average case is a bet, and a bet has terms; quoting one without saying what you assumed about the input is quoting a bet without saying what you wagered on.

The amortised cost answers a third question that sounds like the second and is not: over a whole run of operations, what does each one cost? You met it in Data structures under list.append, which is usually a single cheap store but every so often copies the entire list to a bigger block. Price one append and the answer flickers between cheap and expensive. Price the run:

append: 1,000,000 appends took 51.2 ms total = 51.2 ns each amortised
        over the run: 85 reallocations, 8,445,096 slots copied = 8.45 per append

A million appends, and the total copying they set off comes to about eight and a half slots moved per append — a constant, so each append is O(1) amortised.

Amortised is a guarantee, not a bet

That looks like an average, and confusing the two is the mistake this chapter exists to stop. The average case can be defeated by an unlucky input: hand the dict colliding keys and its O(1) becomes O(n), the bet lost. The amortised bound cannot be defeated by any input. There is no sequence of a million appends that copies more than about a million slots, because the expensive appends are the ones that just doubled the free space, so the cheap appends between them are guaranteed to be numerous enough to pay for the next copy. No distribution, no assumption about the data, no bet — a worst-case guarantee, spread evenly over the sequence that earned it.

That is the difference in one line. Average is a claim about which inputs you expect. Amortised is a claim about a sequence of operations that holds for every input. They both "average out," which is how they blur together, and they answer different questions, so the confusion is expensive.

So when you say an operation is O(1), the honest follow-up is which question? Reach for the worst case when one slow call is a problem you cannot absorb. Reach for the average case when you can state the distribution you are betting on and live with being wrong sometimes. Reach for the amortised cost when you run an operation in bulk and one occasional expensive step is bought and paid for by the cheap ones around it. Every complexity claim in the rest of this guide is one of these three, and the first thing to ask of any of them is which.

Recursion is frames on a stack, and the stack has a floor

How deep can Python recurse before it breaks? Most people answer 1000, because that is what sys.getrecursionlimit() says, and it is wrong in more than one way. Here is a function that recurses as deep as it can and reports how far it got:

default limit 1000: deepest frame index reached = 996

Close to 1000, a few short because the machinery that caught the error was itself a few calls deep. Now raise the limit to two hundred thousand and run the same recursion in a fresh process:

pure-Python, limit 200_000 -> rc 0 | depth reached: 199998 | peak RSS KiB: 61400

rc 0 is a clean exit. Two hundred thousand levels deep, no crash, about sixty megabytes of memory used. So the 1000 was never a ceiling — it was a guard rail, and you can move it. To understand what it is guarding against, and why the answer is not simply "move it higher", you have to look at what a single call actually is.

A call is a box, and the boxes stack

When a function is called, the machine sets aside a small block of memory for that one call: its arguments, its local variables, and — the part that matters — the address to jump back to when the call returns. That block is a frame. Every call in progress has exactly one, and it lives for as long as the call has not yet returned.

Because calls finish in the reverse of the order they started — the most recently called function returns first — these frames are kept on a stack, the last-in-first-out structure from Data structures. Calling pushes a frame on top; returning pops it off. At any instant the stack of frames is the exact chain of "who is waiting on whom": main called parse, which called tokenize, which is running now, three frames deep.

Recursion is what you get when the function on top of the stack is the same function again. There is nothing special about it to the machine — factorial(5) waiting on factorial(4) waiting on factorial(3) is the identical mechanism as three different functions, just with the same code running in each frame. That is the whole of it, and it is worth saying plainly because "a function that calls itself" is a description that hides the cost. Frames on a stack is a description that shows it: the space a recursion uses is one frame per level, times its depth. A recursion n levels deep is holding n frames at once, and that is a number you can put your finger on.

The frame is a real object with a real size. CPython will tell you: sys.getsizeof on a frame reports 168 bytes for the Python-level object, and the two hundred thousand frames above cost about sixty megabytes of heap all told — a few hundred bytes each, once you count everything hanging off them. That is why the recursion survived: sixty megabytes is nothing, so a deep pure-Python recursion is a memory question with a comfortable answer.

The floor you fall through without an exception

So why guard it at 1000 at all? Because there is a second ceiling, and it does not raise an exception — it ends the process. Recurse with something that calls into C on every single level, here an __eq__ comparison on a deeply nested object, and watch:

C-mediated recursion -> rc -11 (-11 = SIGSEGV) | built |

The object built fine; the comparison did not. rc -11 is not a Python error you can catch. It is the operating system killing the process with signal 11, SIGSEGV — a segmentation fault, the process reaching past the memory it was given. There is no traceback, no RecursionError, no except that fires. The interpreter is simply gone.

What it ran out of is the C stack: a single fixed region, 8 MiB on this machine, that the C code underneath the interpreter uses for its frames. Every level of C-mediated recursion consumes a slice of it, and when the slice count crosses the region's size, the next write lands outside and the kernel pulls the trigger. Binary-search for the exact depth and this machine gives:

deepest C-mediated (__eq__) recursion that survives: 15392; 15393 segfaults
=> about 545 bytes of C stack per level of C-mediated recursion

15,392 levels live, 15,393 dies on this run; the exact boundary shifts by a few each time you try it, because the stack starts in a slightly different place, but it always lands near fifteen thousand. Divide the 8 MiB region by that depth and you get about 545 bytes of C stack burned per level — the real ceiling, far below the 200,000 the pure-Python recursion sailed to.

Why the same recursion has two fates

Two ceilings, then, and the puzzle is why the pure-Python recursion cleared 200,000 while the C-mediated one died at 15,392. The answer is a change in CPython 3.11, and the release notes state it directly:

During a Python function call, Python will call an evaluating C function to interpret that function's code. This effectively limits pure Python recursion to what's safe for the C stack. In 3.11, when CPython detects Python code calling another Python function, it sets up a new frame, and "jumps" to the new code inside the new frame. This avoids calling the C interpreting function altogether. Most Python function calls now consume no C stack space.

Before 3.11, every Python call also grew the C stack, so both ceilings were really the one 8 MiB floor and deep recursion segfaulted. Since 3.11, a Python function calling another Python function stays on the Python side and touches only the heap, so 200,000 frames cost sixty harmless megabytes. But the moment a level passes through C — a comparison, an index, a __hash__, anything that calls a C function that then calls back into Python — that level pays the 545 bytes of C stack again, and a deep enough recursion of that shape still finds the floor. sys.setrecursionlimit moves the Python guard rail; it does not move the floor, and raising it past what the C stack can hold turns a catchable RecursionError into an uncatchable crash.

If you genuinely need the depth, the floor itself can be raised — run the recursion in a thread created with a larger stack, and a 512 MiB thread stack lets the same function hit the recursion limit instead of the segfault. But the honest fix for deep recursion is usually to stop recursing and use an explicit stack, or an iterative loop, precisely because the floor is real and silent.

Reach for this understanding whenever a recursion is more than shallow: the depth is a real count of real frames, the space cost is that count times a few hundred bytes, and there are two ways to hit bottom — a RecursionError you can catch and design around, and a segfault you cannot. Knowing recursion is frames on a stack is also what lets you count it, and counting it — turning a recursion's shape into a cost — is the next chapter.

A recursion tree is a recurrence you can read

Here is the definition of the Fibonacci numbers, written as the recursion everyone writes first:

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

How many calls does fib(34) make? Each call makes two more, so the reflex answer is about 2³⁴ — seventeen billion. Count them:

   n    naive calls   memo calls          ratio  calls/phi^n
  25        242,785           26          1.618        1.447
  26        392,835           27          1.618        1.447
  27        635,621           28          1.618        1.447
  28      1,028,457           29          1.618        1.447
  29      1,664,079           30          1.618        1.447
  30      2,692,537           31          1.618        1.447

At n = 34 it is 18 million, not 17 billion — off by a factor of nearly a thousand. The reflex was wrong, and the shape of the error is the whole content of this chapter. To count a recursion you draw its tree and read the cost off it, and the tree tells you things the "two calls each" reflex cannot.

From a tree to a recurrence

Draw the calls fib(5) makes as a tree, each call hanging the two it spawns beneath it:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
│     ├─ fib(1)
│     └─ fib(0)
└─ fib(3)
   ├─ fib(2)
   │  ├─ fib(1)
   │  └─ fib(0)
   └─ fib(1)

Every node is one call, so the number of calls is the number of nodes — fifteen for fib(5). And the waste is already visible: fib(3) is computed twice and fib(2) three times, each one a whole subtree redone from scratch. Hold on to that repetition; it is the hinge the end of the chapter turns on.

You do not have to draw the whole thing to size it. Write down what one call costs in terms of smaller calls, and you have a recurrence — an equation that defines the cost T(n) at size n using the cost at smaller sizes. For Fibonacci, one call does a constant amount of its own work and makes two recursive calls, on n − 1 and n − 2:

T(n) = T(n-1) + T(n-2) + 1

That + 1 is the call's own work; the two terms are its children. This is the same equation as the Fibonacci numbers themselves, so the call count grows like Fibonacci grows — and Fibonacci does not grow like 2ⁿ. Look at the ratio column: each call count is about 1.618 times the one before, not 2 times. That number is the golden ratio φ = (1 + √5) / 2 ≈ 1.618, and the reason it is not 2 is that the two branches are not the same size — one recurses on n − 1, the other on the smaller n − 2, so the tree is lopsided and grows more slowly than a tree that always split in two. The last column makes it exact: calls divided by φⁿ is a flat 1.447 at every size. That flatness is why the count is written Θ(φⁿ) and not O(φⁿ): O is only a ceiling, grows no faster than, while Θ says the growth matches φⁿ exactly — a ceiling that is also a floor. The recurrence is the tree, and reading the recurrence is reading the tree without drawing it.

Three shapes, and what each costs

Almost every recursion you meet is one of three tree shapes, and each has a cost you can read straight off its recurrence.

One child, half the size: T(n) = T(n/2) + 1. Each call throws away half its input and recurses on the rest, doing constant work itself. The tree is a single path, and its length is the number of times you can halve n before reaching 1. That count is the logarithm — log₂ n is exactly "how many times can you halve n before you hit 1", the inverse of doubling: 2¹⁰ = 1024, so log₂ 1024 = 10. (The maths guide Shape and change builds this in "The logarithm is the exponent".) So this shape is O(log n), and it is binary search, the next chapter's subject. The worst-case probe counts are the logarithm to the digit:

           n   worst probes   ceil(log2(n+1))
       1,000             10                10
   1,000,000             20                20
1,000,000,000             30                30

A billion items, thirty probes. Doubling the input adds one level, because one more halving reaches the extra layer — that is what logarithmic growth feels like.

Two children, half the size, plus linear work: T(n) = 2T(n/2) + n. Split the input in two, recurse on both halves, then spend n work combining the results. This is merge sort, and its cost is the prettiest in the group. There are log₂ n levels (halving down to 1), and every level does n total work — the top does n, the next does two halves of n/2 which is again n, and so on. n work at each of log₂ n levels is O(n log n):

       n    merge steps      / n   / (n log2 n)   log2 n
    1024         10,240    10.00          1.000       10
    4096         49,152    12.00          1.000       12
   65536      1,048,576    16.00          1.000       16

Total work divided by n is log₂ n exactly. That is why n log n sits just above linear and nowhere near quadratic: it is n work, done a logarithmic number of times.

Two branches that barely shrink: T(n) = T(n-1) + T(n-2) + 1. Fibonacci again — the input drops by one or two per level, so the tree is deep and its width explodes. That is O(φⁿ), exponential, and it is the shape that turns a fifty-line function into a machine that never finishes.

The real one: CPython's own multiply

None of this is confined to textbook recursions. When you multiply two large integers in Python, the interpreter does not use the schoolbook method you learned, which multiplies every digit of one number by every digit of the other — that is n² work. It uses Karatsuba's method, and Karatsuba is a recursion with a recurrence of exactly the split-and-combine shape, but with three recursive calls instead of two. From Objects/longobject.c:

By picking X to be a power of 2, "*X" is just shifting, and it's been reduced to 3 multiplies on numbers half the size.

T(n) = 3T(n/2) + n. Three children, each half the size — and you can read the cost off a stopwatch without knowing the formula. If doubling the input multiplies the time by 3, then each doubling triples the work, and the exponent is whatever power of n triples when n doubles. Time CPython multiplying big integers, doubling the digit count each row:

    digits         ms   ratio vs half
    40,000       3.24            3.07
    80,000       9.66            2.98
   160,000      29.34            3.04
   320,000      88.56            3.02

Every doubling costs almost exactly 3×, not the 4× that n² schoolbook multiplication would cost. Three-per-doubling is n raised to log₂ 3 = 1.585. So list.sort is not the only place the standard library runs an algorithm you can price by reading a recurrence — the * in a * b is a recursion tree with three branches, and its 1.585 exponent is sitting in that ratio column.

The hinge: does the tree repeat itself?

Now look back at the Fibonacci table, at the two call-count columns. Naive: 18 million calls at n = 34. Memoised — the identical recursion, with each answer remembered the first time it is computed — 35 calls, which is n + 1. The recursion did not change. What changed is that the naive tree computes fib(10) thousands of separate times, because fib(10) shows up under fib(11) and fib(12) and everywhere else, and the memoised one computes each distinct value once and reuses it.

That is the hinge the whole back half of this guide turns on. The same recursion is O(φⁿ) or O(n) depending only on whether its subproblems repeat. When the tree is full of duplicated work — the same smaller problem solved over and over — computing each distinct subproblem once collapses an exponential tree to a linear walk. Recognising that a recursion tree repeats itself, counting how many distinct subproblems it really has, and paying for each only once, is dynamic programming, and it is chapter 10. First, the smallest recursion whose whole difficulty is getting one boundary right: binary search.

There is no right binary search, only a right invariant

You know how to write a binary search. It is four lines, you have written it before, and it worked. Here is the one most people write — search a sorted list for the first position at or above x, the insertion point — with hi starting at the last index, the way the textbook picture of "low and high pointers" suggests:

def search(a, x):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else:          hi = mid
    return lo

Now test all four of the searches people actually write against Python's own bisect.bisect_left, exhaustively — every sorted list of length 0 to 5 over the values {0, 1, 2}, every query from −1 to 3, 280 cases in all, with an alarm to catch anything that loops forever:

v1 half-open [lo,hi)      correct on 280/280 cases
v2 closed hi=len-1        correct on 200/280 cases
                          first wrong answer: a=[0] x=1 -> got 0, want 1
v3 <= with hi=mid         correct on 0/280 cases
                          first non-termination: a=[0] x=-1
                          first exception: a=[] x=-1 -> IndexError
v4 mid rounds up          correct on 280/280 cases

The version above is v2, and it is correct on 200 of 280 cases — right 71% of the time. That is the worst possible result, worse than a version that is always wrong, because 71% passes a casual test suite and ships. Look at where it fails: a=[0], x=1, it returns 0 when the answer is 1. The answer is "past the end of the list" — the insertion point is len(a), one past the last index — and hi = len(a) - 1 cannot return it, because it started hi one slot too low. Every case v2 gets wrong is a case where the answer is len(a), and that is precisely the case a hand-written test forgets, because you test for things that are in the list.

The remedy is not care, it is a named condition

You will not fix this by being more careful, because you were being careful. You fix it by stating the one thing that has to stay true, out loud, and letting the code follow from it. That thing is an invariant — a condition you arrange to be true before the loop starts, keep true across every single iteration, and therefore still have true when the loop ends, so that its truth at the end hands you the answer.

For binary search the invariant is a statement about what lo and hi mean. CPython's own bisect writes it as the docstring of the function you were testing against:

The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x.

Read that as the loop's promise about lo and hi: everything before lo is already known to be less than x, and everything at hi or beyond is already known to be at least x. The answer — the first position that is not less than x — is somewhere in the still-unknown middle, [lo, hi). Now the four lines are not choices to get right, they are forced:

• lo, hi = 0, len(a). At the start nothing is known, so the unknown region is the whole list, including the slot past the end. hi is len(a), not len(a) - 1 — that off-by-one in v2 was a violated invariant, not a typo.
• if a[mid] < x: lo = mid + 1. You just learned a[mid] is less than x, so everything up to and including mid is less than x, so lo moves past it. The invariant stays true.
• else: hi = mid. You learned a[mid] is at least x, so mid could be the answer; it joins the "≥ x" region as its first element, hi = mid, never mid − 1.
• while lo < hi. Stop when the unknown region is empty. At that moment lo == hi, and the invariant says everything before it is < x and everything from it on is ≥ x — which is the definition of the answer.

That is v1, correct on all 280. And here is the point the table is really making: v4, which rounds the midpoint up and moves lo = mid instead, is also correct on all 280 — a different interval convention, a different loop body, equally right. There is no single correct binary search. There is a correct pairing of four decisions — the interval's open or closed end, the loop condition, which way mid rounds, and how lo and hi update — and the invariant is the thing that tells you whether a pairing is consistent. Mix them incoherently and you get v3: <= with hi = mid never shrinks the region when lo == hi == mid, so it loops until the alarm fires, or indexes an empty list and throws.

The bug Python is constitutionally unable to show you

There is a second flaw in that midpoint line, and it is the more famous one. mid = (lo + hi) // 2 adds two indices before halving them. In Python that is safe forever, because Python integers grow to whatever size they need. In a language with fixed-width integers — C, Java, Go — lo + hi can exceed the largest value the type holds and wrap around to a negative number. Compile the arithmetic in C with 32-bit ints and watch it happen:

low  = 1073741823
high = 2147483646
(low + high) / 2            = -536870913   <-- negative index
low + (high - low) / 2      = 1610612734

The correct midpoint is 1,610,612,734; the addition gives −536,870,913, a negative index that reads outside the array. This only bites past a billion elements, which is exactly why it survives review and testing for years and then corrupts something in a system large enough to matter.

The thing to sit with is that Python cannot demonstrate this bug, and that is not a reason to relax — it is the reason to be careful. The identical four lines, correct and safe in your Python, are broken in the C or Java port, and no Python test you write will ever reveal it, because Python's integers refuse to overflow. The fix is to never add the two indices. Compute the midpoint as an offset from lo, so the sum is a difference that cannot overflow, or shift instead of dividing. Both fixes ship in real, heavily-used code. OpenJDK's Arrays.binarySearch:

int mid = (low + high) >>> 1;

>>> is Java's unsigned right shift: it halves low + high treating the sum's bits as unsigned, so even if the addition overflowed into the sign bit, the shift recovers the right answer. git computes it the other way, as an offset, in its patience-diff routine:

int middle = left + (right - left) / 2;

right - left is a difference of two in-range indices, so it is in range; halving it and adding left back lands on the midpoint without ever forming the oversized sum. Neither fix is cleverness. Each is an invariant made safe against a machine detail the algorithm's logic never mentioned.

before rotation: in-order [1, 2, 3]  height 3  (root=1)
after  rotation: in-order [1, 2, 3]  height 2  (root=2)

Reach for the invariant whenever a loop is fiddly enough that you are tempted to fix it by staring harder. Write the condition your variables must satisfy as a comment first — everything before lo is less than x — and the initialization, the update, and the stopping test stop being guesses and become the only lines consistent with it. That is the discipline the next chapter carries from one moving boundary to two.

The same invariant runs the sliding window

A rate limiter has to answer one question, fast, on every request: has this client made more than 100 requests in the last 60 seconds? The obvious implementation keeps every timestamp and counts the recent ones each time it is asked:

def allowed(events, limit, window, now):
    return sum(1 for t in events if t > now - window) < limit

It is correct, and it is quadratic. Every call scans the entire history — O(n) in the number of stored events — and you call it once per event, so draining a stream of n requests is O(n²). At two hundred thousand requests it is already too slow to run on the full stream; the measurement below only cross-checks it against the first 4,000, because past that it is not worth waiting for. The recompute-from-scratch is doing the same work over and over, and the fix is the invariant discipline from the last chapter, moved from one boundary to two.

The window is two boundaries with a promise between them

Binary search kept a single moving boundary and an invariant about everything on either side of it. A sliding window keeps two boundaries — a front and a back — bounding a contiguous run of the sequence, and an invariant about what lies between them. Here the run is "the timestamps still inside the last 60 seconds", the two boundaries are the two ends of a deque, and the invariant is one sentence:

class SlidingWindow:
    # invariant: q holds exactly the timestamps in (now - window, now], oldest first
    def __init__(self, limit, window):
        self.q = deque(); self.limit = limit; self.window = window

    def allow(self, now):
        while self.q and self.q[0] <= now - self.window:   # restore the invariant
            self.q.popleft()
        if len(self.q) < self.limit:
            self.q.append(now); return True
        return False

Write the invariant as a comment and the method has no decisions left in it. When a request arrives at time now, some timestamps at the front of the queue may have aged out of the window — the invariant says they must not be there, so the while loop pops them off the front until the oldest survivor is inside the window again. Now the queue holds exactly the events in the last 60 seconds, so its length is the count the naive version computed by scanning, and the decision is len(self.q) < self.limit. The deque — the double-ended queue Data structures built for exactly O(1) work at both ends — appends the new timestamp at the back and pops expired ones off the front, and neither end shifts the other.

Run it against the naive version on a real arrival stream and it agrees, at a fraction of the cost:

  200,000 arrivals over 66,496 s, limit 100 per 60 s -> 109,502 allowed
  deque version agrees with the O(n)-per-call naive version on the first 4,000: True

The nested loop that is not quadratic

Look at allow again and something should worry you. There is a while loop inside the method, and the method is called once per event. A loop inside a per-event call is the exact shape of the O(n²) you were trying to escape — it looks like the naive scan wearing a different coat. Predict its cost and the honest first guess is quadratic.

It is O(n) for the whole stream, and the reason is the amortised argument from chapter 1. Do not count the pops per call — count them per timestamp, over its whole life. Each timestamp is appended to the queue exactly once, when its event arrives, and popped from the queue exactly once, when it ages out. It cannot be popped twice; once it is gone it is gone. So across all two hundred thousand calls, the total number of pops the while loop ever performs is at most two hundred thousand — one per timestamp — no matter how they cluster. A single allow call might pop fifty expired timestamps at once, but only because fifty earlier calls each appended one and popped none. Spread the popping over the calls that paid for it and every call is O(1) amortised, exactly the way an occasional expensive append was paid for by the cheap ones around it. The nested loop is real; the quadratic cost is not, because the invariant guarantees each element crosses each boundary once.

That "each element enters once and leaves once" is the signature of the whole technique, which generalises past time windows. The pattern is called two pointers: two indices walking through a sequence, never backtracking, with an invariant maintained on the region between them. A window over the last k seconds is one instance; finding the longest substring with no repeated character is another (advance the front, and when a duplicate appears advance the back past it); merging two sorted lists is a third. In every case the two pointers between them sweep the sequence once, and what would have been an O(n²) recompute at each position collapses to O(n) because the work done at the boundaries is bounded by how many times an element can cross them, which is once.

Reach for a sliding window whenever the question is about a contiguous run of a sequence — a time window, a substring, a subarray — and the naive answer recomputes that run from scratch at every position. State what must be true of the region between your two pointers, maintain it as they move, and let the amortised argument tell you the cost: if each element enters and leaves the window a bounded number of times, the whole sweep is linear, however nested the code looks. The invariant is doing the same job it did in binary search — it is just holding a region together now instead of splitting one apart.

No comparison sort beats n log n, and here is why

This chapter has the one piece of genuinely beautiful theory in the guide, and the reason to trust it is that a machine can be made to agree with it exactly. The claim is a limit on what is possible: no sort that works by comparing elements — merge sort, quicksort, heapsort, bubble sort, anything that asks "is this one smaller than that one?" — can guarantee fewer than about n log n comparisons. Not "no known sort"; no possible one. That is a strong thing to assert, so it has to be earned.

A sort is a tree of yes/no questions

Start with what a comparison sort is allowed to know. It never looks at an element's value directly; its only instrument is a comparison, which returns one bit — yes or no, a < b or not. So picture the entire algorithm as a tree of those questions. At the top it asks one comparison. The answer, yes or no, sends it down one of two branches, where it asks another, and so on. Every path down the tree is one possible run of the sort, and at the bottom of each path is a leaf: the specific rearrangement the sort commits to once it has asked enough questions to be sure. This is a decision tree, and it is not a metaphor — it is the shape of the algorithm's logic, with the branching made visible.

Here is the whole tree for sorting three elements a, b, c:

                     a < b ?
                yes /       \ no
              b < c ?         a < c ?
            y /     \ n      y /     \ n
          abc     a < c ?  bac     b < c ?
                 y /   \ n         y /   \ n
               acb    cab        bca    cba

Six leaves at the bottom: abc, acb, cab, bac, bca, cba. That number is forced, and it is the crux of the whole argument. To sort correctly the tree must have a leaf for every possible starting order of the input, because two different starting orders need two different rearrangements to fix, and a leaf commits to exactly one rearrangement. Miss an ordering and there is some input the sort gets wrong. So the tree needs at least as many leaves as there are orderings of n things.

That count is the factorial, written n!: the number of distinct orders n things can be in. Three things have 3! = 3 · 2 · 1 = 6 orders — the six leaves above. Five things have 5! = 120. The factorial explodes: 10! is over three million, 20! is past a billion billion, because each new element multiplies in one more choice of where it goes.

The height of the tree is the number of comparisons

Now count comparisons. The number of questions the sort asks on its worst input is the length of the longest path from the top of the tree to a leaf — the tree's height. And a binary tree cannot be both short and bushy: each question only doubles the number of leaves you can reach, so a tree of height h has at most 2^h leaves. Turn that around. To hold n! leaves you need height at least log₂(n!) — the power you must raise 2 to before it reaches n!. So every comparison sort, on its worst input, makes at least log₂(n!) comparisons. There is no arrangement of the questions that escapes it, because the leaves have to be there and the tree has to be tall enough to reach them all.

The last step is to see that log₂(n!) is the n log n from the chapter title. There is a classical approximation for it (Stirling's), but you do not need the formula — you can just watch the two quantities sit almost on top of each other:

   n               n!     log2(n!)      n log2 n
   8           40,320         15.3          24.0
  12      479,001,600         28.8          43.0
 100                -        524.8         664.4
1000000                - 18,488,884.8  19,931,568.6

At a million elements log₂(n!) is 18.5 million and n log₂ n is 19.9 million — within seven percent, and the gap is a constant factor that Big-O throws away. They are the same growth shape. So the floor under every comparison sort is Θ(n log n), and merge sort, which hits n log n, is not merely good — it is within a constant factor of the best any comparison sort can ever be.

The bound is not loose — a machine checks it

You might suspect log₂(n!) is a soft floor that no real sort quite reaches, the way theoretical bounds often are. It is not, and this is the part worth the chapter. Search the space of all possible comparison strategies exhaustively — for each n, find the strategy whose worst case is as good as possible, by minimax over every way the comparisons could branch — and compare that true optimum S(n) against the bound:

  n        n!   ceil(log2 n!)   true optimum S(n)   gap
  3         6               3                   3     0
  4        24               5                   5     0
  5       120               7                   7     0
  6       720              10                  10     0

Gap zero. For every n up to 6, the best possible comparison sort needs exactly ⌈log₂(n!)⌉ comparisons — the ⌈ ⌉ is 'round up', since you cannot make a fraction of a comparison. The information-theoretic bound is not just a lower limit, it is achieved. A brute-force search over every conceivable sorting strategy agrees with the counting argument to the integer. (The exact bound stays reachable only for small n; beyond that the search space is astronomical and this run stops at 6. It is enough to see the argument is tight, not merely suggestive.)

The three classic sorts, and quicksort's real worst case

With the floor established, count what the textbook sorts actually spend. Here are merge, quick, and heap sorting the same 8,192 elements, once random and once already in order, against the floor of 94,685 comparisons:

algorithm                          random   already sorted
merge sort                         96,199           53,248
quicksort (last pivot)            123,633       33,550,336
quicksort (random pivot)          123,542          116,854
heapsort                          187,734          194,316

On random data all three are within a small factor of the 94,685 floor — merge sort is almost exactly on it. Then look at the quicksort row on already-sorted input: 33,550,336 comparisons, which is n(n−1)/2, the sum 1 + 2 + ⋯ + (n−1). That is O(n²), the quadratic shape from the very first chapter, and it appears on the tidiest input imaginable.

This is the fact most courses bury under "average case O(n log n)". Quicksort works by picking a pivot and splitting the rest into "less" and "greater". Pick the last element as the pivot — the textbook default — and on already-sorted data the pivot is always the largest element, so "less" gets everything and "greater" gets nothing. The split does not divide the problem; it shaves one element off, and the recursion is n levels deep doing n work each. The catastrophe is not an adversary who crafted a pathological input. It is sorted input, the most common shape real data arrives in — after a previous sort, after an ORDER BY, after anything that already put things in order. Quicksort's worst case is the everyday case, exactly the way the plain binary search tree's was in Data structures.

The fix is in the next row: choosing the pivot at random drops the sorted-input count from 33 million back to 116,854, next to the floor again. A random pivot cannot be reliably fed its own worst case, because the input no longer decides the split — a coin does. That is the whole reason production quicksorts randomise or take a median-of-three, and it is the first hint that how you choose inside an algorithm can matter more than the algorithm's name.

So the bound gives you two durable things. It tells you n log n is the floor for anything that sorts by comparing, so a sort that must go faster has to stop comparing altogether — which is the next chapter. And it reframes a "worst case" from a curiosity into a real input shape you can name and check for, because the worst case that bit here was not exotic. It was a list that happened to already be in order.

list.sort is smarter than the bound, and sometimes you can beat it

The last chapter proved a floor: no comparison sort can guarantee fewer than about n log n comparisons. For 100,000 elements that floor is 1,516,704. So how does Python's list.sort get away with this?

input shape             comparisons   / log2(n!)
random                    1,528,966        1.008
already sorted               99,999        0.066
reversed                     99,999        0.066

On random data it makes 1,528,966 comparisons — 1.008 times the floor, so close to optimal it is almost touching it. But on already-sorted or reversed input it makes exactly 99,999, which is n − 1, a hundredth of the floor. The proof is not broken. The floor is a worst-case bound — the best you can guarantee across all inputs — and real inputs are not worst cases. They arrive with order already in them, and Python's sort is built to find that order and charge you only for what is genuinely out of place.

Timsort merges the runs already in your data

The algorithm is Timsort, and its own design document states the trick in the first paragraph:

This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

"Natural mergesort" is the key phrase. Instead of blindly splitting the array in half the way textbook merge sort does, Timsort walks the array once and notices the runs — the stretches that are already ascending or descending. Reversed input is one long descending run, which it flips in place; sorted input is one long ascending run it leaves alone; and either way it has sorted the whole array with a single pass of n − 1 comparisons and no merging at all. On real data — log lines mostly in time order, records mostly sorted by the key you last sorted them by — it finds several long runs and merges those, paying only for the disorder. That "as few as N-1" is not marketing. It is the 99,999 in the table.

The merge order was subtly wrong, and a proof caught it

Once you have runs, you have a decision the textbook never faces: in what order do you merge them? Merge the wrong pairs and you copy short runs into long ones over and over; merge well and you barely touch each element. Timsort keeps a stack of pending runs and merges them by a policy, and that policy is where the interesting thing happened — the same design document tells the story:

The original version of this code used the first thing I made up that didn't obviously suck ;-) It was loosely based on invariants involving the Fibonacci sequence. It worked OK, but it was hard to reason about, and was subtle enough that the intended invariants weren't actually preserved. Researchers discovered that when trying to complete a computer-generated correctness proof.

Read that against chapter 4. The merge policy had invariants it was supposed to maintain — conditions about the run lengths on the stack that were meant to hold after every merge — and they were not actually being preserved. Nobody noticed by testing, because the sort still produced correct output; it just occasionally merged badly. What noticed was a machine trying to prove the invariants held, and failing, because they did not. That is precisely what the invariant discipline buys you that testing cannot: a test checks the cases you thought of, and a proof checks all of them at once, so a proof can find the case where your stated condition quietly breaks. The repair, from Python 3.11 onward, is a policy called powersort with a cleaner invariant — the run stack's "powers" are kept strictly decreasing — that is provably near-optimal. If you are on Python 3.10 or earlier, your list.sort still runs the old Fibonacci-flavoured policy; the powersort merge order is a 3.11-and-later fact, and it is the kind of change that never shows up in your code and silently improves every sort you run.

To beat the bound, stop comparing

Timsort is near-optimal, and near-optimal for a comparison sort is still n log n on genuinely random data. The only way underneath that floor is to stop comparing — because the floor was proven only for sorts that compare, and an algorithm that never asks "is a < b?" is not bound by it.

Counting sort is the cleanest example. If your keys are integers in a known small range [0, k), do not compare them to each other. Make an array of k counters, walk the input once tallying how many times each value appears, then walk the counters emitting each value that many times:

def counting_sort(a, k):
    counts = [0] * k
    for x in a:            # one pass: tally
        counts[x] += 1
    out = []
    for v in range(k):     # emit each value counts[v] times, in order
        out.extend([v] * counts[v])
    return out

There is not a single < in it. It uses each key as an array index — the O(1) arithmetic addressing from Data structures — so its cost is O(n + k): one pass over the n inputs, one pass over the k counters. When k is small next to n, that is effectively O(n), linear, below the comparison floor. And the payoff is real enough to survive a fifty-fold interpreter handicap. Here is a pure-Python counting sort against C's compiled Timsort, on a million integers:

values in [0, 256)
  sorted()      (Timsort, C)             104.4 ms
  radix LSD     (pure Python)             62.4 ms
  counting sort (pure Python)             29.3 ms

values in [0, 4,294,967,296)
  sorted()      (Timsort, C)             300.1 ms
  radix LSD     (pure Python)            574.6 ms

When the keys are bytes, k = 256, pure-Python counting sort finishes in 29 ms against compiled Timsort's 104 — 3.6× faster, despite running in the interpreter. The asymptotically-better algorithm wins, and wins big. Then change one thing — draw the keys from the full 32-bit range — and the same idea inverts. Counting sort with four billion counters is not even attemptable, and its cousin radix sort, which sorts digit by digit from the least-significant up (the LSD in the table), does more passes than Timsort saves and loses by nearly two to one. The k in O(n + k) is the range of the keys, not the count of distinct ones, and when the range explodes the + k is the whole bill. This is the trie lesson from Data structures wearing new clothes: the algorithm that is better on paper is better only inside a condition, and the condition here — keys drawn from a small range — is one you can check before you choose.

What your sort actually runs

The bound also quietly explains why almost no standard library ships plain quicksort, whose sorted-input catastrophe you saw last chapter. Every one of these was read from source at a pinned version:

The V8 file is worth a second look: its header carries the Python Software Foundation copyright and says it "was first implemented in python", so the .sort() in your browser is a translation of the same Timsort as your Python. And glibc's qsort, the C standard library's sort, is not quicksort at all — it is mergesort, falling back to heapsort only when it cannot allocate scratch space. The lesson to carry out of the sorting chapters is not a favourite algorithm. It is that sorted() being stable (equal elements come out in the order they went in) is a language guarantee you can build on — the docs promise it — while which algorithm delivers it is an implementation fact that changes under you, and the good ones change toward beating the bound on the ordered data you actually have.

Every algorithm is one of five moves

Here is a scheduling problem you have, in some form, already solved by hand. You have a list of maintenance windows — jobs with a start hour and an end hour — and one worker who can run one at a time. Which jobs do you accept to fit the most of them in? Take five windows:

jobs: [(2, 6), (6, 9), (10, 11), (11, 14), (9, 15)]
largest compatible set: [(2, 6), (6, 9), (10, 11), (11, 14)]  (4 jobs fit)

Four fit; (9, 15) is the odd one out, because it collides with three of the others. That answer is correct, and the way it was computed is the most important algorithm in this chapter even though it is the one you will use least: brute force. Try every possible subset of the jobs, throw away the ones with an overlap, and keep the largest of what remains. It cannot be wrong, because it literally checks every option — brute force is the definition of the answer, run as code.

It is also the slowest thing you could do. A set of n jobs has 2ⁿ subsets, so the cost doubles with every job added:

  n= 4  2^n =           16 subsets
  n=12  2^n =        4,096 subsets
  n=20  2^n =    1,048,576 subsets

Twenty jobs is already a million subsets. This is the whole tension of the back half of the guide, in one problem: brute force is the answer you can always reach and can never afford, so every other technique is a way of getting the same answer while looking at far less of that 2ⁿ.

The ladder, and the question at each rung

The named algorithm paradigms are usually taught as a taxonomy — here is divide and conquer, here is greedy, memorise the definitions. That is the wrong shape. They are a ladder, ordered from most general and slowest at the top to most specialised and fastest at the bottom, and you descend it by asking one question at each rung: does my problem have the structure this cheaper technique needs? If yes, you drop a rung and pay less. If no, you stay where you are. Brute force is the top rung, always correct, always available, and the descent is a series of trades of generality for speed.

Brute force → divide and conquer. Ask: can I split the problem into independent subproblems and combine their answers? If the pieces do not interact — sort the left half and the right half, then merge — you get the split-and-combine recurrence from chapter 3 and an n log n where brute force was exponential. Merge sort and Karatsuba's multiply are this rung. When the pieces do interact, you cannot cleanly divide, and you stay up top.

Divide and conquer → greedy. Ask: is a locally-best choice always safe? If at each step you can grab the most attractive option and never regret it, you skip searching entirely — one pass, n log n or better. For the scheduling problem the answer is yes, and a one-line rule matches the brute-force optimum on every instance. But "always safe" is a claim that has to be proved, not tested, and that proof is the whole of the next chapter, because the rules that merely seem safe are the ones that quietly cost you.

Greedy → dynamic programming. Ask: do the subproblems overlap, and does an optimal solution contain optimal solutions to them? When a greedy choice is not safe but the problem still breaks into subproblems that recur — the same smaller question asked over and over, the repetition you saw in the Fibonacci tree — you compute each distinct subproblem once and build up. That is chapter 10, and the scheduling problem walks straight into it the moment you add one number to each job.

Dynamic programming → backtracking. Ask: can I build a solution one piece at a time and abandon a partial build the instant it cannot work? When you genuinely must explore many combinations but most branches die early, you walk the space of possibilities as a tree and prune the dead limbs before descending them. That is still exponential in the worst case — it is brute force with a conscience — but the pruning is often the difference between a second and a year. Chapter 11.

Why the top rung stays

The reason to start every problem at brute force is not thoroughness for its own sake. It is that the brute-force solution is where you find the structure that lets you descend. Writing "try every subset" forces you to state exactly what a valid answer is and how to score it, and that statement is what you then inspect for a safe greedy choice, or overlapping subproblems, or a prunable tree. Skip it and reach straight for a clever technique, and you routinely reach for the wrong one — a greedy rule that is not actually safe, a dynamic program whose state you never pinned down. The brute force is also your test oracle: it is slow but unarguably correct, so you can check the fast version against it on small inputs, which is exactly how every failure count in the next three chapters was produced.

So the procedure is not "know the five paradigms". It is: write the brute force, confirm it is correct, and then walk down the ladder asking whether your problem's structure earns each drop. The interval-scheduling problem you just brute-forced is the worked example for the next two rungs — greedy in chapter 9, and then, with a single number added, dynamic programming in chapter 10. Same problem, three rungs, and the questions above are what move you between them.

Greedy is a proof, not a heuristic

The scheduling problem from the last chapter has a greedy solution: make the locally-best choice at each step and never reconsider. But which local choice? Two rules sound equally sensible. Take the job that finishes earliest, so the worker frees up soonest. Or take the shortest job, so it consumes the least time. Both are greedy, both are one line, and both pass a quick test. Run each against the brute-force optimum on four thousand random instances:

  earliest finish    wrong on     0/4000   (never wrong)
  earliest start     wrong on   564/4000
  shortest first     wrong on    65/4000

Earliest-finish-first is wrong on zero instances. Shortest-first is wrong on 65 — 1.6%. That number is the trap. It is small enough that shortest-first sails through a handful of hand-written test cases, ships, and quietly returns a suboptimal schedule on one instance in sixty for the rest of its life. "It worked on my test data" is not evidence that a greedy rule is correct; a rule that is wrong 1.6% of the time works on almost all your test data. Testing cannot tell 0 from 65. Only a proof can, and this is the chapter where greedy stops being a hunch and becomes something you can establish.

Watch shortest-first fail

Here is one of the 65, so the failure is concrete rather than statistical:

jobs: [(9,14),(1,5),(1,7),(9,12),(0,3),(11,15),(6,11)]
  shortest-first picks  [(9,12), (0,3)]              -> 2 jobs
  earliest-finish picks [(0,3), (6,11), (11,15)]     -> 3 jobs

Shortest-first grabs the two briefest windows, (0,3) and (9,12), and having taken (9,12) it has blocked the whole 9-to-15 stretch, so nothing else fits and it stops at two. Earliest-finish takes (0,3), then the earliest-finishing job that still fits — (6,11) — then (11,15), and lands three. The short job (9,12) looked cheap and was expensive, because it sat in the middle and fenced off more than its length. Duration was the wrong thing to be greedy about. Finish time was the right thing. Nothing in the rules themselves tells you which; you have to reason about why one choice is safe.

The exchange argument

The reason earliest-finish is safe is an exchange argument, and it is the standard way to prove any greedy algorithm correct. The shape of it is always the same: show that whatever the best possible solution does, you could exchange its first step for the greedy step without making it any worse — so there is a best solution that agrees with greedy, and by repeating the argument, greedy is a best solution.

Run it here. Let g be the job that finishes earliest of all, the one greedy takes first. Take any optimal schedule — the genuine best, however it was built — and look at its first job to finish, call it j. Two cases. If j is g, the optimal schedule already agrees with greedy on the first pick. If j is not g, then g finishes no later than j by definition, so g cannot overlap anything the optimal schedule ran after j — everything after j started at or after j finished, which is at or after g finished. So you can lift j out and drop g in, and the schedule is still valid and still exactly the same size. You have exchanged the optimal's first job for the greedy job and lost nothing.

So there is always an optimal schedule that starts with g. Now delete g and the jobs it blocks, and you have a smaller scheduling problem with the identical structure; the same argument says greedy is safe on its first pick too, and the next, all the way down. That induction is the proof. It is not a claim that earliest-finish usually wins — it is a demonstration that it can never lose, which is exactly the thing the 0/4000 was hinting at and could never establish on its own, because no number of passing tests rules out the failing case. The exchange argument is what separates a greedy algorithm from a greedy guess.

One extra number, and greedy dies

Now change the problem by the smallest amount that breaks it. Each job is worth something — a value, not just a slot — and you want the schedule of maximum total value rather than maximum count. Same jobs, same overlaps, one number added. Every greedy rule you can invent falls over:

  greedy: highest value first    wrong on   368/4000
  greedy: best value/hour        wrong on  1015/4000
  DP (the right method)          wrong on     0/4000

Take the highest-value job first? Wrong 368 times — a fat job can block two medium ones worth more together. Take the best value-per-hour? Worse, 1,015. There is no exchange argument to be had, because no local choice is safe: the right decision about one job depends on the combinations of the others it does or does not rule out, and greedy, which never reconsiders, cannot see combinations. The only rule that is never wrong is the last one, marked DP, and it is not greedy at all.

That is the cleanest bridge in the guide from one paradigm to the next. A single added number turned a problem where a locally-best choice is provably safe into one where no locally-best choice exists, and the technique that survives the change is dynamic programming. Reach for greedy when you can prove — by an exchange argument or its kin — that the local optimum is globally safe, and treat any greedy rule you have only tested as unproven, because 1.6% wrong looks exactly like 0% wrong until the instance that bites you. When the proof will not come, the reason is usually that the choices interact, and that is the signal to climb down to the next rung.

Dynamic programming is counting states before you write code

Every dynamic programming tutorial shows you a finished recurrence and derives a table from it, which teaches the wrong lesson: it makes the recurrence look like the hard part and the table like bookkeeping. The recurrence is the easy part. The hard part, the part that decides whether the whole approach is even viable, is counting the states, and there is a procedure for it that almost nobody teaches. This chapter runs that procedure on a program you use every day.

That program is git diff. Under it is one of the oldest dynamic programs there is: the longest common subsequence, or LCS — the longest run of lines that appears in both files in the same order, though not necessarily adjacently. Everything the diff doesn't highlight is the common subsequence; everything else is an add or a delete. Here is the brute-force recursion for its length, and it is short enough to hold in your head:

def lcs(i, j):                       # length of LCS of A[:i] and B[:j]
    if i == 0 or j == 0: return 0
    if A[i-1] == B[j-1]: return 1 + lcs(i-1, j-1)   # lines match: take it
    return max(lcs(i-1, j), lcs(i, j-1))            # they don't: drop one side

If the last lines of the two prefixes match, they belong to the common subsequence and you recurse on what is left of both. If they do not, the answer is the better of dropping the last line of one file or the other. This is correct, and it has optimal substructure: the best answer is built from best answers to smaller versions of the same problem, which is the first thing dynamic programming requires. It is also, run as written, a disaster.

The same subproblem, two million times

Take a real diff: CPython's listsort.txt at 3.10 against 3.11 — the very change that replaced Timsort's merge policy with powersort from chapter 7. Window the recursion tightly around the first line that differs and count how many calls the naive version makes, against how many distinct subproblems actually exist:

  window   distinct states      naive calls   calls per state
       6                49            1,847              37.7
      12               169        3,756,150          22,225.7
      16               289      587,666,073       2,033,446.6

At a window of sixteen lines there are 289 distinct subproblems and the recursion makes 587 million calls — it computes each subproblem two million times over. The state space grew quadratically (289 is 17²) while the call count grew exponentially, and the gap between those two curves is the entire opportunity.

This reframes what memoisation is, and the reframe is the point. People describe memoisation as "caching that makes an exponential algorithm polynomial", as if you bolted an optimisation onto a slow algorithm. That is backwards. The algorithm was always polynomial in its distinct states — there are only 289 of them. The exponential blow-up is nothing but revisiting those 289 states two million times each. Memoisation does not speed up the algorithm; it stops you redoing work you already did, by remembering each subproblem's answer the first time and returning it every time after. Seen that way, the natural question is not "how do I cache this?" but "how many distinct states are there?" — and that question is a procedure.

The procedure, in five steps

Here is the method the tutorials skip, in order. It produces your complexity before you write a line of dynamic-programming code.

1. Write the brute-force recursion. No cleverness, no table — the four lines above.
2. List its arguments. For lcs they are i and j. That tuple — the arguments the recursion branches on — is the state. Nothing else about the computation matters to its cost.
3. Count the distinct states. i runs 0…|A| and j runs 0…|B|, so there are (|A|+1) × (|B|+1) of them. For these two files, 764 × 803 = 613,492.
4. Multiply by the work per state. Each lcs(i, j) does a constant amount of its own work — a comparison and a max. So the whole thing costs about 613,492 × O(1) ≈ 613,492 steps. That is your complexity, and you now know it before writing any table.
5. Only now choose how to fill it — top-down or bottom-up.

Step 4 is the one that is never taught and the one that matters most, because it tells you whether the approach is viable at all. If counting the states had given you a trillion, you would know to stop and find a different formulation before investing in code. The state count is the go/no-go, and it falls out of the recursion's argument list almost mechanically. The recurrence was never the hard part.

Top-down, bottom-up, and the row you can throw away

With 613,492 states confirmed affordable, step 5 offers two ways to visit each once. Memoisation (top-down) keeps the recursion and wraps it in a cache. Tabulation (bottom-up) throws the recursion away and fills a table in an order that guarantees each cell's dependencies are ready before it. Identical complexity, identical answer — the textbooks say pick either. Measure them:

  memoised (top-down)        LCS =  718   cells held =   613,492   best of 3 =   424.6 ms
  tabulated (full table)     LCS =  718   cells held =   613,492   best of 3 =    72.5 ms
  tabulated (two rows)       LCS =  718   cells held =     1,606   best of 3 =    68.6 ms

All three find the same 718 common lines. But tabulation is 5.9× faster than memoisation on this machine, for two mechanical reasons: every memoised call pays Python's function-call overhead and a cache-key hash, where the table is a flat loop over an array, and the memoised recursion also risks the 8 MiB C-stack floor from chapter 2 on a large enough input, which the loop cannot. So "pick either" is wrong on wall-clock and wrong on robustness.

The third row is the prettier win. Look back at the recurrence: lcs(i, j) depends only on row i and row i−1, never on anything two rows back. So you never need the whole 613,492-cell table in memory at once — you need the current row and the previous one. That rolling-row trick drops the space from 613,492 cells to 1,606, a 382× reduction, for the identical answer, and it is available only because you built the table bottom-up where the dependency order is visible. This is why the choice in step 5 is not a shrug: tabulation is faster, safer, and it opens the space optimisation that memoisation cannot.

The payoff is that you now know what your tools do. git diff computes a diff with an LCS-family algorithm — its source cites "An O(ND) Difference Algorithm and its Variations", by Eugene Myers — and git diff --patience switches to a different dynamic program built on longest increasing subsequence, applying "the well-known Myers algorithm" only between the unique lines it anchors on. The diff you read a dozen times a day is a dynamic program, and the --patience flag is you choosing a different one. Reach for dynamic programming when a problem has optimal substructure and its subproblems overlap (the same smaller question asked repeatedly, the repetition you first saw in the Fibonacci tree), and before you write any of it, run the five steps: the state is the recursion's argument list, and counting it tells you the cost while it is still cheap to change your mind.

Backtracking is a search tree you prune

Here is a regular expression that will take down a web server. It is not malformed, it is not exotic, and a reviewer would wave it through:

      n      seconds   ratio vs n-1
     24       0.6427           1.98
     26       2.5862           2.00
     28       9.4360           1.93

Twenty-eight as and one !, and the match takes nine and a half seconds of pure CPU. Each added character almost exactly doubles the time — 0.6, 2.6, 9.4 — so thirty-five characters would run for minutes and forty for hours. If that pattern sits anywhere user input can reach it, a thirty-character string is a denial-of-service attack that fits in a tweet. This is a real, named vulnerability class, and to see why it happens you have to see what the regex engine is actually doing, because it is running one of the five paradigms from chapter 8.

The engine is walking a tree of choices

Python's re module is a backtracking engine. To match (a+)+ against a run of as, it has to decide how to carve the run into groups: the inner a+ grabs some as, the outer + repeats, and there are many ways to split. Faced with aaaa, the first a+ could take one a, or two, or all four; each choice leaves a different remainder for the next repetition to divide, and so on down. The engine tries one split, and if the overall match fails, it backtracks, undoing its most recent choice and trying the next one, working through the possibilities one at a time.

That is backtracking in general: build a solution one decision at a time, and the instant a partial solution cannot be completed, undo the last decision and try a different one. Drawn out, the decisions form a tree — every node a choice, every path a partial solution, every leaf a complete attempt — and the engine walks it depth-first. Here is the shape, for the smaller job of listing every subset of {a, b, c} by deciding in-or-out for each element:

                     start
              a in /       \ a out
             .              .
          b/   \b out    b/   \
         .      .       .      .
       c/ \   c/ \    c/ \   c/ \
     abc  ab ac  a  bc  b  c   (none)

Eight leaves, 2³, one per subset. Permutations are the same tree with "which unused element goes next?" at each node instead of in-or-out; combinations are the same tree with a rule that prunes any branch that would exceed the size you want. Subsets, permutations, combinations — the three staples of every coding interview — are not three algorithms. They are one depth-first walk over a tree of choices, and they differ only in what each node decides and which branches get cut.

The catastrophe in ^(a+)+$ is that its tree has 2^(n-1) leaves — one for every way to partition n a's into ordered groups — and because the trailing ! guarantees the match fails, the engine is forced to visit all of them before giving up. There is no valid leaf to stop at early, so nothing prunes the tree, and its size is the exponential you measured.

Pruning is the whole game

Backtracking is still exponential in the worst case — it is brute force from chapter 8, walking the same 2ⁿ space. What makes it useful is pruning: cutting a branch the moment it cannot lead to a valid answer, so you never descend the subtree beneath it. A combination search that has already picked more elements than allowed stops there rather than exploring everything below. A good pruner turns a tree with billions of leaves into one with thousands, and the difference between an algorithm that returns in a second and one that runs for a year is almost always how early it prunes, not how fast it visits a node.

The regex has nothing to prune, which is exactly its problem, and the fix is not a cleverer engine — it is a pattern that cannot backtrack. ^a+$ expresses the same intent with no nested quantifier, so there is a single way to match and no tree to explore:

   ^a+$ on 40,001 chars: 0.160 ms

Forty thousand characters in a sixth of a millisecond, against nine seconds for twenty-eight. A regular expression is not a declarative wish you hand to a black box; it is a program that runs a backtracking search, and its cost is a thing you are responsible for. (Some engines, like Go's regexp and RE2, refuse to backtrack at all and guarantee linear time by using a different matching machine entirely — a trade of a few rare features for the elimination of this whole vulnerability.)

The other backtracker you run every week

The second production backtracker is your package manager. When you pip install and watch it download three versions of the same library, that is not thrashing — it is backtracking, and pip's own documentation names it:

During dependency resolution, pip needs to make assumptions about the package versions it needs to install and, later, check these assumptions were not incorrect. When pip finds that an assumption it made earlier is incorrect, it has to backtrack, which means also discarding some of the work that has already been done, and going back to choose another path. This can look like pip downloading multiple versions of the same package … The backtracking of choices made during is not unexpected behaviour or a bug. It is part of how dependency resolution for Python packages works.

Version resolution is the subset tree wearing a suit: each node picks a version for one package, that choice propagates constraints onto the others, and when some package is left with no version that satisfies every constraint, the branch is dead and the resolver walks back to try a different version higher up. A toy resolver over a five-package universe finds a working set — web 3.0, orm 2.0, http 2.1 — after trying only four candidate versions, and the reason it stays that cheap is the pruning heuristic real resolvers use: resolve the most-constrained package first, the one with the fewest surviving candidates, so dead branches are discovered near the top of the tree where cutting them saves the most. That is the same lesson the regex taught by its absence — the search is only tractable because most of the tree gets cut before it is walked.

Reach for backtracking when you genuinely must explore combinations — assignments, orderings, selections under constraints — and cannot prove a greedy shortcut or a dynamic-programming decomposition. Write it as: extend the partial solution by one decision, check whether it can still possibly succeed, recurse if so, and undo the decision on the way back up. The whole art is in that check, because it is what prunes, and the difference between backtracking that finishes and backtracking that hangs is entirely how much of the tree you can refuse to enter. And when you meet it in the wild — a regex, a resolver, a constraint solver — you now know its cost is exponential unless something is cutting the tree, and you know to go find what.

A dependency graph is not a DAG

Every dependency system you have read about is described as a DAG — a directed acyclic graph, dependencies pointing one way, no loops, because a thing cannot depend on something that depends on it. So here is a dependency graph you can check that claim against: the import graph of the Python standard library on this machine, every module a vertex and every import an edge. Data structures built it as an adjacency list — 179 modules, 759 import edges, a dict of neighbours — and left the algorithms that run over it to this guide. Run the first one and the DAG story falls apart:

topological sort: placed 87/179; 92 modules could not be placed
strongly connected components with >1 module: sizes [2, 75]

More than half the modules could not be ordered, and the reason is a strongly connected component of 75 modules — 75 standard-library modules that can all reach each other through imports, os and re and socket and pathlib tangled into one mutual knot. The import graph is emphatically not acyclic. Before that can mean anything, though, you need the two ways to walk a graph, because every fact above came from one of them.

BFS is for fewest hops; DFS is for reachability

There are two fundamental graph traversals, and the difference between them is the difference between the queue and the stack from Data structures.

Breadth-first search visits the graph in rings: all the vertices one hop from the start, then all two hops away, then three. It uses a queue — the FIFO structure — so it finishes with the whole current ring before touching the next, and the payoff is that the first time it reaches any vertex, it arrived by a shortest path. That is what BFS is for: fewest hops. Ask for the shortest import chain between two modules and BFS answers directly:

  logging -> re -> enum      (2 hops)
  http -> enum -> warnings -> re   (3 hops)

logging does not import enum directly, but it imports re, which imports enum — two hops, and BFS found that it is the shortest because it checked everything one hop away first and came up empty. Swap the queue for a stack and the same code becomes depth-first search, which does the opposite: it follows one path as deep as it will go, hits a dead end, backs up one step, and tries the next branch — the backtracking walk from the last chapter, over a graph instead of a solution tree. DFS does not find shortest paths. What it is for is reachability and ordering: it naturally discovers everything downstream of a vertex, and the order in which it finishes vertices is exactly what the next two algorithms need.

Ordering a graph, and discovering you can't

A topological sort is an ordering of the vertices such that every edge points forward — every module appears after everything it imports. It is what a build system computes to know what to compile first, what a task runner uses to schedule jobs with dependencies, what pip needs to install packages in a working order. The cleanest way to build one is Kahn's algorithm: find every vertex with no remaining incoming edges — nothing it still depends on — output it, remove it, and repeat. Each removal may free up others, and you peel the graph layer by layer from its independent leaves inward.

The algorithm carries its own cycle detector for free. If at some point no vertex has zero incoming edges but vertices remain, the leftovers form a cycle — each is waiting on another that is waiting on it, so none can ever be first. That is the 87/179 above: Kahn placed 87 modules and then jammed, because the remaining 92 are inside cycles or downstream of them, and there is no valid order to put a cycle in. A topological sort exists if and only if the graph is a DAG, so a failed topological sort is a proof that it is not one.

To find the actual cycles rather than just their downstream shadow, you need one more algorithm. A strongly connected component is a maximal set of vertices where every one can reach every other, which is exactly a knot of mutual dependency. Tarjan's algorithm finds all of them in a single depth-first walk, and it reported the two above: a small one, codecs and encodings importing each other, and the 75-module giant. Those 75 modules are not badly written — they are the core of the language, and cores are interconnected. The lesson is that "dependency graph" and "DAG" are not synonyms in the real world, and code that assumes acyclicity will hang or crash on the first cycle it meets.

How the stdlib loads anyway, and what you can do with it

If 75 modules import each other in a cycle, how does Python import any of them without chasing the loop forever? The answer is the actionable part of this chapter, and it shows up when you separate the imports that run at module load from the ones tucked inside functions:

module-level imports only:   E = 599   topo places 125/179   ->  54 unplaceable
all imports (incl. deferred): E = 759   topo places  87/179   ->  92 unplaceable

Counting only the imports at the top of each file — the ones that actually execute when the module is first loaded — the graph has 160 fewer edges and far fewer modules stuck in cycles: 54 instead of 92. Those 160 missing edges are deferred imports, import statements written inside a function body instead of at the top of the file. An import inside a function does not run until the function is called, which is typically long after both modules have finished loading — so that edge simply does not exist in the import-time graph, and the cycle it would have closed is broken at the moment that matters.

This is a fix you can apply this week. When two of your own modules need each other and Python raises an ImportError about a partially-initialised module or a circular import, you do not have to redesign the dependency structure. Move one of the two imports off the top of the file and into the function that actually uses it. You have deleted an edge from the import-time graph — turned a cycle into a path for the purpose of loading — while keeping the dependency available at call time, which is exactly the trick the standard library uses 160 times to load itself.

Reach for BFS when the question is fewest hops — shortest path in an unweighted graph, degrees of separation, minimum number of steps — because the queue guarantees it. Reach for DFS when the question is reachability or ordering — what can this reach, is there a cycle, what is a valid sequence — and build topological sort and strongly-connected-components on top of it. And carry the one fact that the tidy diagrams omit: real dependency graphs have cycles, so the engineering worth knowing is not how to sort a clean DAG but how to detect a cycle and how to break it. The next chapter adds a number to every edge, and the traversal stops being about hops and starts being about cost.

Dijkstra trusts a node once, so one negative edge breaks it

Dijkstra's algorithm finds the shortest path in a weighted graph, and it is fast because it is decisive: it commits to each node's distance the moment it reaches it and never looks back. That decisiveness is its whole speed and its one fatal assumption. Here is a four-node graph where the assumption fails — the cost in cents to move a job between processing queues, where one hop earns a rebate, so a single edge is negative:

edges: [('in','fast',1), ('in','meter',2), ('meter','fast',-2), ('fast','out',1)]

   pop (0, in) -- finalise in at 0
         relax in->fast: dist[fast] = 1
         relax in->meter: dist[meter] = 2
   pop (1, fast) -- finalise fast at 1
         relax fast->out: dist[out] = 2
   pop (2, meter) -- finalise meter at 2
         relax meter->fast: dist[fast] = 0
   pop (0, fast) -- already finalised, SKIPPED
   pop (2, out) -- finalise out at 2

  node      Dijkstra   Bellman-Ford   true shortest
  out              2              1               1   <-- WRONG

Dijkstra says the cheapest route to out costs 2. It costs 1 — go in → meter → fast → out for 2 + (−2) + 1 = 1. The algorithm did not crash or loop; it returned a confident, plausible, wrong number. To see why, and why it is not a bug but a broken precondition, you have to see what Dijkstra is actually doing with the heap from Data structures.

The algorithm, and the one claim it rests on

Dijkstra keeps a tentative distance to every node and a min-heap — the priority queue you built in Data structures, which hands back the smallest item in O(log n) — holding the nodes it has reached, keyed by their tentative distance. The loop is three steps: pop the nearest unfinalised node off the heap, finalise it (declare its tentative distance final), and relax its outgoing edges — for each neighbour, check whether reaching it through the just-finalised node is cheaper than its current tentative distance, and if so, lower it and push it on the heap. Repeat until the heap is empty. Every node comes out of the heap in order of increasing distance, closest first.

The finalise step is the daring one, and it rests on a single claim: once a node is popped, its distance can never improve. Dijkstra bets that the first time it pops a node, it already has that node's true shortest distance, so it can finalise and move on without ever reconsidering. That bet is what lets it touch each node once instead of iterating, and it is sound — provided every edge weight is non-negative. Here is the argument. When you pop node v as the closest remaining node at distance d, any other route to v must go through some node still on the heap, all of which are at distance ≥ d, and then traverse at least one more edge. If edges cannot be negative, that other route costs at least d plus something non-negative, so it cannot beat d. The node is safe to finalise. The whole correctness of Dijkstra is that one paragraph.

Where a negative edge falsifies it

Now read the trace against that paragraph. Dijkstra pops fast at distance 1 and finalises it — committing, on the strength of the non-negative assumption, that no cheaper route to fast exists. But a cheaper route does exist: through meter, which has not been popped yet, using the −2 edge. Two pops later meter is finalised at 2 and relaxes meter → fast, discovering dist[fast] = 0 — but it is too late. fast was finalised at 1, so when it is popped again the algorithm skips it (already finalised, SKIPPED), and every distance computed from the stale fast = 1 is wrong, including out, which was priced off it as 1 + 1 = 2 before the real value of 0 was known. The negative edge made a later route cheaper than a finalised distance, which is precisely the situation the correctness argument assumed away. Nothing in the code detects this; the algorithm simply trusts a node it should not have.

This is not "Dijkstra gives a slightly worse answer with negative edges". It gives a wrong answer, silently, because its founding invariant was violated — the same lesson as chapter 4, one level up: an algorithm is only as correct as the condition it maintains, and feeding it input that breaks the condition does not make it degrade gracefully, it makes it lie. (Not every negative edge triggers the failure — one placed where it never undercuts a finalised node leaves the answer intact — which is worse, not better, because it means testing on a graph with negative edges can pass and hide the bug.)

Bellman-Ford pays more and assumes less

The fix is to stop finalising early. Bellman-Ford makes no bet about pop order; it simply relaxes every edge in the graph, and repeats that V − 1 times. The logic is plodding and bulletproof: after one full pass, every shortest path that is one edge long is correct; after two passes, every two-edge path; and since no shortest path in a graph of V nodes has more than V − 1 edges, V − 1 passes settle everything, negative edges included. On the four-node graph it returns out = 1, the true answer. The cost of assuming nothing is the runtime — O(V·E) against Dijkstra's near-O(E log V), materially slower on a big graph — which is exactly why you reach for Dijkstra when you can and pay for Bellman-Ford only when you must.

Bellman-Ford also answers a question Dijkstra cannot even represent. Run that V − 1-pass loop one more time, and if any distance still drops, there is a negative cycle — a loop whose edges sum to less than zero, which you could ride forever to make the path arbitrarily cheap, so "shortest path" stops being well-defined. Bellman-Ford detects it and says so; Dijkstra has no concept of it, because it never revisits a finalised node.

A* is Dijkstra with a hint

Dijkstra explores outward in every direction equally, because it has no idea where the goal is — it pops the globally-nearest node, north, south, or backward. If you do know roughly where the goal lies, you can aim. A* adds a heuristic h(n), an estimate of the remaining distance from n to the goal, and orders the heap by "distance so far plus estimated distance to go" instead of distance so far alone, so it prefers nodes that look like progress toward the target. On a 200×200 grid with obstacles, the effect is dramatic:

heuristic                           path cost   cells expanded  % of grid
h = 0  (this IS Dijkstra)                 398           31,066      77.7%
h = Manhattan (admissible, tight)         398           17,222      43.1%
h = 3 x Manhattan (inadmissible)          450              594       1.5%

The first row, h = 0, is Dijkstra exactly — with no hint, A* is Dijkstra, and it expands three-quarters of the grid to be sure. A good hint (Manhattan distance, the grid-steps to the goal ignoring walls) roughly halves the work and finds the identical optimal path of 398. The condition that keeps the answer optimal is admissibility: the heuristic must never overestimate the true remaining cost. An admissible heuristic can make A* prefer promising directions but never fools it into abandoning a genuinely shorter route, so the path it returns is still optimal — 398, every time.

The last row shows what breaking admissibility buys and costs. Multiply the estimate by three and A* becomes wildly overconfident about paths that point at the goal, expanding just 594 cells — 52 times fewer than Dijkstra — and returning a path of 450, thirteen percent too long. That is the entire trade of A* in one table: h = 0 is Dijkstra, slow and always right; an admissible heuristic is faster and still right; an inadmissible one is faster still and wrong, and how wrong is exactly how much it overestimates. Reach for Dijkstra when weights are non-negative and you have no sense of direction, Bellman-Ford when weights can go negative or you must detect a negative cycle, and A* when you can cheaply estimate the remaining distance and want to aim the search — keeping the estimate admissible if the answer has to be optimal, and relaxing it deliberately, eyes open, only when a good-enough path found fast beats the best path found slow.

Union-find is almost linear, and "almost" has a number

Here is the same algorithm run twice on the same input — fifty thousand elements, a hundred thousand merge operations — the only difference being two optimisations, each a single line, switched off and then on:

variant                                          pointer hops    hops/op   seconds
neither optimisation                              532,075,228    5320.75    21.070
union by rank only                                    300,509       3.01     0.055
path compression only                                 535,498       5.35     0.070
path compression + union by rank                      174,757       1.75     0.049

Five hundred and thirty-two million pointer hops become a hundred and seventy-five thousand — 3,044 times fewer — and twenty-one seconds become five hundredths of one. Two lines of code did that, and the reason they can is a piece of complexity theory with a punchline you can compute: the optimised structure is almost exactly linear, and "almost" turns out to be a specific, tiny number.

The structure, and the two lines

Union-find (or disjoint-set) answers one pair of questions over a changing collection of groups: are these two elements in the same group? and merge these two groups. It is what you reach for when connectivity arrives incrementally — network components as links come up, pixels joined into regions, "are these two accounts already linked?" as links are added. Each element points at a parent; follow parents up and you reach a root that represents the whole group. find(x) walks to the root; union(a, b) merges two groups by pointing one root at the other. Two elements are in the same group exactly when they have the same root.

The naive version is O(n) per find, because nothing stops the parent chains from growing into long spindly threads — merge in the wrong order and finding a root means walking half the elements, which is the 532 million hops above. The two optimisations attack the chain length directly:

• Union by rank. When merging, always hang the shorter tree under the taller one, never the reverse. A tree only gets taller when two equally-tall trees merge, so heights stay logarithmic instead of linear.
• Path compression. Every time find walks from a node up to the root, point every node it passed directly at the root on the way back. The chain you just paid to climb is flattened, so the next find on any of those nodes is one hop.

Each helps enormously alone — either one drops the hop count by more than a thousandfold — and together they nearly eliminate the walk: 1.75 hops per operation, flat, and it stays flat as the structure grows.

The number "almost" hides

With both optimisations, the total cost of m operations on n elements is O(m · α(m, n)), where α is the inverse Ackermann function. That bound is worth stating carefully, because it is easy to garble: it is a bound on the whole sequence of m operations, not a promise that each individual operation is O(α) — a single find can still be slow, but across any run of m of them the average is α, which is amortised cost from chapter 1 wearing its most extreme form. And α is not merely small. It is the slowest-growing function you are ever likely to meet, and you can watch why by computing the function it inverts.

The Ackermann function A(m, n) grows faster than any tower of exponentials. Compute it at a few points:

   A(0,1)=2   A(1,1)=3   A(2,1)=5   A(3,1)=13
   A(4,1) = 2^65536 - 3, a number with 19,729 decimal digits
   first 40 digits: 2003529930406846464979072351560255750447 ...

A(4, 1) is already a nineteen-thousand-digit number. The inverse, α(n), runs the other way: it asks how many levels of that explosive hierarchy do you climb before you pass n? — and because each level is so vast, the answer barely moves:

   alpha(10)                        = 3
   alpha(100)                       = 4
   alpha(1,000,000)                 = 4
   alpha(1,000,000,000)             = 4
   alpha(18,446,744,073,709,551,616) = 4

That last input is 2⁶⁴, the largest value a 64-bit machine can hold — a twenty-digit number — and α of it is 4. It has to be, because the level-four threshold, A(4, 1), has nineteen thousand digits, so nothing a 64-bit computer can even represent gets past level four. This is the honest content of "almost linear": α(n) ≤ 4 for every input any real machine will ever process, so union-find is linear for all practical purposes — and yet α is not a constant, it does eventually reach 5 and 6 and beyond, at input sizes with more digits than the universe has atoms, so the structure is provably not linear. Both halves are true, and computing α is what lets you hold them at once: a bound that is four in practice and unbounded in theory.

Kruskal is union-find plus a sort

Union-find's best-known use turns a graph into its cheapest skeleton. A spanning tree connects all V vertices using V − 1 edges and no cycle; a minimum spanning tree is the cheapest such — the least total edge weight that still holds the graph together, which is the question behind "what is the cheapest set of links that keeps every region connected?". Kruskal's algorithm builds it with the greedy discipline of chapter 9: sort every edge cheapest-first, and add each edge unless its two endpoints are already connected — because adding an edge inside an existing group would make a cycle. "Already connected?" is exactly find(a) == find(b), and "connect them" is union(a, b), so union-find is the entire engine:

   eu-west   -- eu-central   $45
   us-east   -- us-west      $120
   ap-south  -- ap-northeast $150
   us-east   -- sa-east      $160
   us-east   -- eu-west      $210
   us-west   -- ap-northeast $260
   total $945 over 6 links (V-1 = 6); all 12 links = $2635
   exhaustive min over all spanning trees: $945  -> Kruskal optimal: True

Six links, $945, against the $2,635 of connecting everything. Kruskal is greedy — it takes the cheapest safe edge and never reconsiders — so it needs the same kind of guarantee chapter 9 demanded, and here the guarantee is checked directly: enumerate every spanning tree of the graph and the cheapest is $945, the number Kruskal found. The greedy choice is provably safe for this problem, which is why sorting edges and grabbing them cheapest-first, cycle-checking with union-find, is not a heuristic but the actual minimum.

Reach for union-find whenever the question is grouping or connectivity under a stream of merges — connected components, cycle detection while building, "are these two already joined?" — and turn on both optimisations, always, because they cost two lines and buy three thousandfold. And reach for Kruskal when you need the cheapest connecting structure of a weighted graph, remembering it is nothing but this chapter's structure with the edges sorted first.

Trade a right answer for a smaller one

Every structure so far returned the exact answer. This chapter is about a class of algorithms that refuse to, on purpose — they give up being exactly right in exchange for using a fraction of the space, and the trade is not vague hand-waving. Each one has a formula that tells you precisely how wrong it will be, and you can check the formula against a measurement. The reason to end the guide here is that these are the tools that make large-scale systems affordable, and every one is a memory-versus-accuracy dial with the numbers printed on it.

A Bloom filter: membership without storing the members

You want to answer "have I seen this id before?" over a stream of a hundred million items. A set of the ids is exact and costs gigabytes. A Bloom filter answers the same question in a fixed, tiny amount of memory — by being willing to occasionally say "yes" when the answer is "no", and never the reverse.

It is a bit array and k hash functions, nothing else. To add an item, hash it k ways and set those k bits to 1. To test an item, hash it the same k ways and look:

def add(item):
    for h in hashes(item, k):   # k positions
        bits[h] = 1

def probably_contains(item):
    return all(bits[h] for h in hashes(item, k))

If any of the k bits is 0, the item was definitely never added — you would have set that bit — so there are no false negatives, ever. If all k bits are 1, the item is probably present, but those bits could each have been set by some other item, a coincidence that reports a false positive. How often that happens is not a mystery; it is a probability you can compute. A given bit stays 0 only if every one of the kn hash-writes missed it. Each write is independent, and it misses this particular bit with probability 1 − 1/m; independent probabilities multiply, so all kn of them missing is (1 − 1/m)^(kn). For a large bit-count m that is almost exactly e^(−kn/m) — here e ≈ 2.71828 is the natural base of continuous compounding, and that exponential is the one approximation the derivation needs. Guava's BloomFilter writes the finished formula in a source comment it labels the "Cheat sheet":

p = (1 - e ^ (-kn/m))^k

Set the target error, and the formula sizes the bit array. Measure the result against the prediction:

 target p     m bits    m/n   k  predicted p  measured p    bytes
    0.100    479,253   4.79   3      0.10071     0.10167   59,906
    0.010    958,506   9.59   7      0.01004     0.01011  119,813
    0.001  1,437,759  14.38  10      0.00100     0.00104  179,719
  a Python set of the same 100,000 strings: 11,283,410 bytes

Predicted and measured agree to three decimal places at every setting — the theory is not approximately right, it is right. At a one-percent false-positive rate the filter holds a hundred thousand memberships in 119,813 bytes against the set's 11.3 megabytes — 94 times smaller — and it never once claimed a member was absent. (There is a catch the formula makes explicit: the error rate is calibrated for the n you declared. Guava warns that "overflowing a BloomFilter with significantly more elements than specified, will result in its saturation, and a sharp deterioration of its false positive probability" — cram in ten times the items and the bits fill up, and once most bits are 1 almost everything tests positive.)

HyperLogLog: counting distinct things you never store

A Bloom filter tells you whether. HyperLogLog tells you how many distinct — the cardinality of a stream — and it does so in kilobytes no matter how many billions of distinct items go by, storing none of them. The idea is a clever use of chance: hash each item and count the leading zeros in the hash. A hash starting with one zero happens half the time, two zeros a quarter, ten zeros one time in 1024 — so if the longest run of leading zeros you have ever seen is 10, you have probably seen about 1024 distinct items. Rare patterns are evidence of many trials. One such counter is wildly noisy, so HyperLogLog keeps m of them, splits items across them by another slice of the hash, and averages — and averaging m independent estimates cuts the spread by a factor of √m. Redis's implementation pins the numbers:

The use of 16384 6-bit registers for a great level of accuracy, using a total of 12k per key.

Sixteen thousand registers of six bits each is 12 kilobytes, total, to count cardinalities into the billions. The error works out to 1.04/√m, and the measurement lands on it:

  p       m   bytes    1.04/sqrt(m)   measured mean   p90
 14  16,384  12,288        0.00813         0.00635   0.01734

1.04/√16384 = 0.00813, which is the 0.81% that Redis's documentation quotes for PFCOUNT. But read the last two columns together, because this is the trap the docs invite. That 0.81% is a standard error — the typical size of the estimate's miss, not a hard ceiling — and a standard error is a spread, so a good third of readings land further off than it. The p90 here is 1.73%, more than twice the headline: one run in ten is off by over 1.7%. A dashboard built on PFCOUNT that reads "1.2 million unique visitors" is really saying "1.2 million, give or take a percent or two, and occasionally more" — and that is the design working exactly as specified, not a bug. (The maths guide Shape and change builds standard error properly in "What data doesn't tell you"; the two-sentence version is all this needs.)

Count-min never lies low, and reservoir stays fair

Two more, quickly, because they round out the toolkit. A count-min sketch estimates how many times each key appeared (frequencies, not just presence) in a fixed grid of counters. It hashes each key into one counter per row across d rows and increments them; to query, it returns the minimum counter across the rows. Collisions can only ever push a counter up, so the minimum is the least-polluted estimate, and it therefore never underestimates. Its error is bounded: at most ε·N over the true count, with probability 1 − δ, for a grid of width ⌈e/ε⌉ and depth ⌈ln(1/δ)⌉ (ln is the logarithm base e). Checked on 1.4 million requests across 50,000 keys, the bound holds on every single key and no key is ever undercounted:

  eps=0.001  w=2,719 d=5  table=13,595 counters | max overcount 697 | bound eps*N=1,413 | over bound: 0/50000 | undercount: False

Fourteen thousand counters stand in for an exact table of 50,000 entries, and the guarantee is one-sided and provable: you might be told a key is more frequent than it is, never less. And reservoir sampling keeps a fair random sample of k items from a stream whose length you do not know in advance: a log you cannot buffer, an event firehose. Hold the first k; for the i-th item after that, keep it with probability k/i, evicting a random current member if you do. The magic is that this leaves every item, early or late, with the identical chance of being in the final sample — where the expected count of any item, its long-run average over many runs weighted by probability, comes out equal. Across 200,000 trials of a 20-item stream into a 5-slot reservoir, every item was selected almost exactly its fair share, and a chi-square test of uniformity passes comfortably.

Reach for these whenever an exact answer costs more memory than the question is worth, and the application can absorb a quantified, one-directional error: a Bloom filter in front of an expensive lookup to skip the ones that are certainly absent, HyperLogLog for unique counts on a dashboard, count-min for heavy-hitter detection in a rate limiter, reservoir sampling to sample an unbounded stream. Each is the same move — spend a right answer to buy a smaller structure — and because each comes with a formula you can check, the error is a design parameter you set, not a surprise you discover. That move, memory traded against accuracy with the exchange rate written down, is where this guide meets the systems half that comes next: these are the structures that sit in front of caches and behind analytics, and Systems design uses them as known tools.

Which pattern does this problem want

The whole guide taught you patterns. The skill it was actually building is the one this chapter names: looking at a problem you have never seen and knowing, from its shape, which pattern it wants. That recognition is not memory (you cannot memorise problems, there are too many); it is reading a signature. Almost every problem announces its pattern in how it phrases the question, and once you learn the tells, the pattern falls out before you have written a line.

The signature table

Here is the map from what a problem asks for to the pattern that answers it and what that pattern costs. Read it as a set of tells, not a taxonomy to memorise — you have already built every row.

The tells are worth saying out loud, because they are what you actually pattern-match on under pressure. "Sorted", "in order", "top-k", "median" points at sorting or a heap. "Maximum", "minimum", "longest", "fewest" points at greedy or dynamic programming, and which one turns on whether a local choice is safe. "All", "every", "count the ways", "generate" points at backtracking. "Path", "connected", "reachable", "depends on", "cycle" points at a graph. "Approximately", "at scale", "streaming", "how many unique" points at the probabilistic structures. The phrasing is the pattern, most of the time.

When the table runs out

The table stops where a problem gets unusual, so carry the procedure that built it — four questions that place almost anything, and they are the questions this guide has been drilling.

What shape is the answer? Not the algorithm — the output. An ordering, a single optimum, all the valid configurations, a path, a yes/no, a count. The shape of the answer picks the family off the table above, because sorting produces orders, dynamic programming produces optima, backtracking produces enumerations, and graph search produces paths. This is the first cut and it is usually enough to narrow five paradigms to one or two.

What is n, and where on the curve are you? The first chapter's warning is the one everyone forgets in a round: Big-O describes the curve at scale and lies about the small end. If n is twenty, an exponential backtracking solution is instant and correct and the "better" polynomial one is wasted cleverness; if n is a billion, an O(n²) that passed every test is an outage. Ask the size before you optimise, and when two approaches are close on paper, remember the constant the notation threw away can decide it — so measure when you can.

Write the brute force, then ask what lets you descend. The eighth chapter's move: the brute-force solution is always your first correct answer and your test oracle, and writing it is what exposes the structure you exploit to go faster. With it in front of you, walk down the ladder — are the subproblems independent (divide and conquer), is a greedy choice provably safe (greedy), do the subproblems overlap (dynamic programming), does the search tree prune (backtracking)? You descend a rung only when the structure earns it.

Prove it or price it before you trust it. A greedy rule you only tested is unproven, because 1.6% wrong looks exactly like 0% wrong until the instance that bites — so demand an exchange argument. A dynamic program you have not counted might not fit — so count the states before writing the table. And every cost you quote should name which question it answers: worst, average, or amortised. Correct first, then fast, then priced — in that order, because a fast wrong answer is worth nothing and a right answer whose cost you cannot state is a liability.

What is actually being assessed

That procedure is usually framed as interview technique, and it is worth being honest about the interview, because the honest version is more useful than the folklore. There is no single "algorithms round" any more. The format ranges from a 45-minute whiteboard problem to a paid day of shipping real code, and some well-known engineering organisations have removed the algorithms round entirely and say so in public. PostHog's handbook is blunt about it:

No whiteboarding or brain teasers.

Sourcegraph's pairing session is explicitly "not used for technical evaluation"; Artsy's design hour tells you "you will not be asked to code anything." What is assessed, though, is strikingly consistent across every published rubric, and it is exactly the four questions above turned into behaviour. PostHog again, describing what separates a strong candidate:

The strongest candidates slow down before they speed up. They ask clarifying questions. They scope the problem. They decompose it into pieces they can reason about individually.

And on what they are grading:

Brush up on fundamentals, not trivia. … A thoughtful wrong turn that you recover from tells us a lot.

Establish the problem before attacking it. Say why you chose what you chose — "Postgres because the access patterns are relational", not just "Postgres". Notice your own wrong turn and recover from it. Know the cost of what you wrote. None of that is a trick for a whiteboard; it is the discipline of doing the work well, and it survives however the format changes and even as the tools change. The one AI policy published in full draws its line not at using the tools but at understanding: you may build with AI, but "you need to understand what you've built … If you can't defend and explain your solution, it won't matter how polished it looks."

So the thing to carry out of this guide is not a catalogue of algorithms to recite. It is the habit the four questions encode: read the problem's shape, size it honestly, get a correct version before a fast one, and be able to say what everything costs and why you chose it. That is what a good round measures because it is what good engineering is, and you now have every pattern underneath it — built, measured, and priced — rather than handed to you cold.

Further reading

Primary sources, one line each on what it is good for. Every number in this guide traces to one of these or to a script re-run on the machine it was written on.

• CPython source, at tag v3.11.15 — Objects/listsort.txt is Timsort's own design document, the 3.11 switch to powersort included; Objects/listobject.c and Objects/longobject.c hold the merge and Karatsuba code; Lib/bisect.py states the binary-search invariant as a postcondition; Doc/whatsnew/3.11.rst explains why pure-Python recursion stopped consuming C stack.
• OpenJDK, at tag jdk-21+35 — java/util/Arrays.java carries the >>> 1 midpoint fix that exists because of the overflow bug; java/util/TimSort.java is the same sort with the pre-powersort merge policy and a source-comment citation of the correctness-proof paper.
• git, at tag v2.45.0 — xdiff/xdiffi.c names the Myers algorithm behind git diff; xdiff/xpatience.c is the longest-increasing-subsequence variant behind git diff --patience.
• Redis hyperloglog.c (7.2.4) and the PFCOUNT documentation — the register count and the 0.81% figure, stated there as a standard error and not a bound.
• Guava BloomFilter.java (v33.2.1) — the "cheat sheet" comment with the false-positive and optimal-k formulas, and the saturation warning.
• Munro and Wild, Nearly-Optimal Mergesorts (ESA 2018) — powersort, the merge policy CPython adopted in 3.11; named in listsort.txt.
• The public engineering handbooks of PostHog, Sourcegraph and Artsy — three companies that publish their whole interview process, and a check on what a rubric actually measures.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (4th ed., MIT Press, 2022) — the formal proofs under the intuition here: recurrences, the sorting lower bound, greedy and the exchange argument, dynamic programming, the graph algorithms, and union-find.