Algorithms — the art of doing more with less

00What "fast" really means

Before you can make code fast, you have to agree on what "fast" is — and the obvious answer, seconds on a stopwatch, is a trap. This chapter builds the yardstick every other chapter in this volume will use: not seconds, but a count of the work an algorithm does as its input grows. By the end you will be able to look at a loop, count its operations without running it, predict whether it will still be alive at ten million items, and know exactly why "it runs fine on my laptop" is the most expensive sentence in software.

The stopwatch is a liar

Here is the same tiny function — add up the numbers 0, 1, 2, … n-1 — timed seven times in a row on one machine, doing identical work each time.

import time

def work(n):
    total = 0
    for i in range(n):     # exactly n additions, every single run
        total += i
    return total

n = 2_000_000
for _ in range(7):
    t0 = time.perf_counter()
    work(n)                # the identical call, the identical work
    ms = (time.perf_counter() - t0) * 1000
    print(round(ms, 1))    # 67.3 · 67.4 · 68.5 · 67.2 · 68.1 · 67.7 · 66.6

Line by line: work(n) runs a loop that does the same n additions no matter what. time.perf_counter() reads a high-resolution clock before and after; the difference, times 1000, is milliseconds. We ran it and got seven different numbers — 66.6 ms up to 68.5 ms — for byte-for-byte the same work. That spread was only about 3% here because the machine was nearly idle; open a browser, start a video call, or run this on a loaded server and the slowest reading can be several times the fastest. (These are wall-clock times on one specific Intel machine — yours will differ, which is exactly the point.)

Why does the clock wobble? Recall Volume 1's machine: the CPU runs at some clock rate, keeps hot data in a small fast cache, and — crucially — is shared. The operating system constantly pauses your program to let other processes have the core. So the seconds you measure are really operations × time-per-operation, and that second factor is set by the hardware and by whatever else the machine happens to be doing this millisecond. Change the laptop, change the load, change nothing at all and run it again — the seconds move. Seconds measure the kitchen, not the recipe.

If seconds are the wrong yardstick, what is the right one? The blue number that never flinched →

Count the work, not the clock

The fix is to stop timing and start counting. Pick the operations the algorithm actually performs — a comparison, an addition, a swap, a pass of the loop — and count how many it does as a function of the input size. That count is a fact about the algorithm. It doesn't care about your clock speed, your cache, or the video call in the background. Run it on a supercomputer or a calculator from 1995 and the count is the same integer.

Two words we will lean on for the whole volume. n is the size of the input — the number of songs in the playlist, rows in the table, pixels in the image. It is the one knob everything turns on. A basic operation is a single step we agree to treat as one unit of work. Now count the sum loop:

def work_counted(n):
    total = 0
    ops = 0
    for i in range(n):
        total += i
        ops += 1           # tally one addition per pass
    return ops

print(work_counted(10))         # 10
print(work_counted(2_000_000))  # 2000000  — the same on every machine, every run

The loop body runs once per value of i, and there are n values, so it does exactly n additions. We didn't time anything — we counted. For n = 10 the answer is 10; for n = 2,000,000 it is 2,000,000; three runs in a row gave the identical number. This algorithm's cost is n. Double the input, double the work. That sentence — "double the input, double the work" — is a complete, machine-independent description of how this code behaves, and we got it without a stopwatch.

It's the growth that bites, not the number

Knowing an algorithm costs "1000 operations at n = 1000" is nearly useless on its own. The question that matters is: when n gets bigger, how fast does the cost grow? Because inputs always get bigger. Today's 1000 songs are tomorrow's million. Watch what happens when we put one loop inside another — the playlist code that compares every song against every other song, to find duplicates say:

def nested_ops(n):
    ops = 0
    for i in range(n):
        for j in range(n):    # a full inner sweep for EVERY outer step
            ops += 1
    return ops

for n in (5, 100, 1000):
    print("n =", n, " single loop:", n, " nested:", nested_ops(n))
# n = 5     single loop: 5     nested: 25
# n = 100   single loop: 100   nested: 10000
# n = 1000  single loop: 1000  nested: 1000000

The outer loop runs n times; for each of those, the inner loop runs a full n times — so the body fires n × n = n² times. We ran it: at n = 5 the two loops are close (5 vs 25). At n = 100 they are 100 vs 10,000. At n = 1000 they are 1000 vs a million. The single loop and the nested loop start life as near-neighbours and end up in different universes. That divergence — not any single value — is what decides whether your code survives success.

Fine — count the operations and watch the growth. But count for which input? The luckiest one, or the cruelest? →

Best, worst, average — plan for the bad day

Most algorithms don't do the same amount of work on every input of size n. Search a playlist for one song, top to bottom, stopping when you find it. If it's the first track, you make one comparison. If it's the last — or missing — you make n. Same code, same n, wildly different cost, depending on the arrangement of the data. So we name three cases.

def scan(playlist, target):
    comparisons = 0
    for song in playlist:
        comparisons += 1
        if song == target:
            return comparisons     # found it — stop early
    return comparisons             # fell off the end — not found

data = list(range(1000))                   # a 1000-item playlist
print(scan(data, 0))       # 1     BEST:    target is first
print(scan(data, 999))     # 1000  WORST:   target is last
print(scan(data, 1234))    # 1000  WORST:   target isn't there at all
from statistics import mean
print(mean(scan(data, s) for s in data))   # 500.5  AVERAGE over all present items

Best case is the luckiest input — target first, 1 comparison; the smallest cost the algorithm can get away with. Worst case is the cruelest — target last or absent, all 1000 comparisons; the most it can ever be forced to do. Average case is the expected cost over typical inputs: we searched for each of the 1000 present songs once and the mean was 500.5 comparisons — roughly n/2, which makes sense because a random hit lands halfway down on average. All three are real, verified numbers from the run above.

Now we can state the yardstick precisely — and use it to defuse the most dangerous sentence a programmer ever says →

"It runs fine on my laptop"

Here is the whole chapter's payoff, and it is genuinely scary. Take that nested n² loop. On this machine each inner step costs about 28 nanoseconds (measured: the n = 1000 run took 28.2 ms for a million steps). Now watch what the same code does as we feed it more data:

per_op = 28.16e-9              # seconds per inner step, measured on this machine

for n in (100, 10_000, 10_000_000):
    steps = n * n              # the nested loop runs the body n × n times
    seconds = steps * per_op
    print(n, steps, seconds)
# n=100        steps=10,000              -> 0.0003 s      a blink
# n=10,000     steps=100,000,000         -> 2.8 s         a pause
# n=10,000,000 steps=100,000,000,000,000 -> 2,816,000 s ≈ 32.6 DAYS

The demo runs at n = 100 and finishes in a third of a millisecond — instant. Ship it. Then real data arrives: ten million items. The input got 100,000× bigger. But the work — n² — got 100,000² = ten billion times bigger, and the "instant" program now needs a month to finish a single run. Nobody changed a line of code. For contrast, a single pass over those same ten million items (cost n, not n²) took 312 ms in our test — the smarter algorithm is roughly nine million times faster on the exact same hardware. That gulf is what this volume is for.

So the real skill isn't timing code. It's reading its shape before it ever runs. That's a way of thinking — let's name the move →

The one question that turns a coder into an engineer

Everything so far collapses into a single reflex. When you meet a piece of code, a beginner asks "how long did it take?" — a question about the kitchen, whose answer changes with every machine and every mood. The engineer asks "how does its cost grow as n grows?" — a question about the recipe, whose answer is fixed forever. That swap, from measuring the run to reading the growth, is the mental move this whole volume installs. It is why we could predict a 32-day runtime without waiting 32 days.

The idea that you could separate the algorithm from the machine like this is not obvious — it had to be invented. It's the heart of what's called asymptotic analysis, brought into computing and championed by Donald Knuth in The Art of Computer Programming: judge an algorithm by how it behaves as n heads toward infinity, and let the constant, machine-specific noise fall away. The way of thinking underneath is worth stealing wholesale: to understand a system, find the one variable it scales with, then ask what happens when you push that variable to the extreme.

And you already do this off the computer. Deciding whether to phone ahead or just drive to five shops; sensing that inviting "a few more" people is fine but inviting "everyone" is not; knowing a chore that's quick for one week's laundry becomes a nightmare for a year's — that's growth-rate intuition, and you run it every day without naming it. This volume makes it exact, and gives it a language.

We have the idea: count operations, watch the growth, design for the worst case. Now we give that growth a precise name and a notation — meet Big-O, the symbol that lets you say "n²" out loud and have every engineer on earth know exactly what you promised. That's Chapter 01. →

01The growth zoo — Big-O, and its cousins

Here is the promise of this chapter: by the end you will be able to look at a piece of code and say, out loud, how its cost grows — instantly, without running it, without a stopwatch. You will know why we throw away the "3" in 3n² and the whole +100n+7 behind it, and why that is not sloppiness but the deepest honesty about what will actually break at scale. And you will meet the growth zoo — nine animals from the tame O(1) to the monstrous O(n!) — and learn, on sight, which cage your algorithm is in.

Complexity is a price tag, not a stopwatch

A stopwatch measures this run, on this machine, this second. Move the same code to a laptop twice as fast and the number halves. That number tells you almost nothing durable. What an engineer needs is the thing that doesn't change when you swap machines: how the work grows as the input grows. That is time complexity, and the language for it is Big-O.

The unit is not seconds — it is operations: comparisons, additions, array reads, the elementary steps the machine actually takes. Call the input size n (the length of the playlist, the number of users, the pixels in the frame). Then ask a single question: if I double n, what happens to the number of operations? Linear search through an n-song playlist does, worst case, n comparisons — double the playlist, double the work. We write that O(n) and read it "order n". The machine's speed sets how many operations fit in a second; Big-O sets how fast that count climbs. Those are two different facts, and Big-O is the one that decides whether your program survives contact with a big n.

So Big-O keeps the shape and drops the machine. But it drops something else too — it throws away most of the formula. Watch why that is the honest thing to do →

Why we throw away the constants and the small terms

Suppose you count a routine's operations exactly and get f(n) = 3n² + 100n + 7. Big-O reports just O(n²) — it deletes the coefficient 3, the entire 100n term, and the +7. That looks like vandalism. It is not. At the scale where performance actually matters, one term eats all the others alive. Let's not assert it — let's count it.

def cost(n):
    return 3*n**2 + 100*n + 7          # an exact op-count, three terms

for n in (1, 100, 1000, 1_000_000):
    total       = cost(n)
    square_part = 3*n**2               # just the n² term
    print(n, f"{100*square_part/total:6.4f}%  is the n² term")

# 1         2.7273%  is the n² term
# 100      74.9869%  is the n² term
# 1000     96.7740%  is the n² term
# 1000000  99.9967%  is the n² term

Line by line: cost(n) returns the full three-term count. For each n we compute the total, then isolate square_part — the contribution of the n² term alone — and print its share of the whole. The story is in the last column. At n=1 the n² term is a rounding error: 2.7% of the work. By n=1000 it is 96.8%. At a million it is 99.9967% — the 100n and the +7 together are three parts in a hundred thousand. Reporting anything but n² would be describing the dust and ignoring the mountain. That is the rule, and now you have watched it become true: keep only the fastest-growing term, and drop its constant multiplier, because the constant shifts the curve up and down but cannot change which term wins the race to infinity.

Read the code: count the deepest nest

You almost never count exact operations. You read structure, and three rules cover most code you will ever meet:

• Sequential blocks add. Do an O(n) pass, then another O(n) pass — that's n + n = 2n, which is O(n). Work done one-after-another sums, and the sum's Big-O is just its biggest piece.
• Nested loops multiply. A loop over n inside a loop over n runs the inner body n × n = n² times. Each level of nesting multiplies in another factor of n. Three deep is O(n³).
• Halving gives log n. A loop that throws away half of what's left each step reaches the end in log₂ n steps, not n. That's the whole magic of binary search.

Which leaves one sticky-note rule to rule them all: find the most deeply nested piece of work, count how many times it runs, and that dominates the answer. Everything shallower is a lower-order term you're about to drop anyway.

The halving one deserves proof, because log n is the hinge that separates "instant" from "impossible" all over this volume. Watch a million collapse to a handful of steps:

n = 1_000_000
steps = 0
while n > 1:
    n //= 2          # throw away half of what's left, every step
    steps += 1
print(steps)         # 19        ← that's it. one million → 19 steps
import math
print(math.log2(1_000_000))   # 19.931568569324174

Line by line: we start at a million and keep integer-halving until nothing is left to split. It takes 19 steps — because log₂(1,000,000) ≈ 19.93, and you can't take a fraction of a step. Halving is a doubling running backwards: 2¹⁰ ≈ a thousand, 2²⁰ ≈ a million, 2³⁰ ≈ a billion. Every time you multiply n by a thousand, a halving algorithm needs only ten more steps. That is why a database can find one row among a billion with about thirty comparisons — and why binary-searching your bug (delete half the code, does it still break?) beats reading every line.

Three rules, and you can read most code's cost off its shape. But "O(n) worst case" hid a word — worst. What about the best case, and the typical one? Meet Big-O's two cousins →

Big-O, Ω, Θ — the upper, the lower, the tight

Big-O is precisely one thing: an upper bound. "This algorithm grows no faster than g(n)." It is a promise about the ceiling — the worst that can happen. But a full description of an algorithm has three walls, and they have three names:

• O (Big-O) — the ceiling. Grows no faster than this. The worst case. "It will never be slower than O(n)."
• Ω (Big-Omega) — the floor. Grows no slower than this. The best case. "It can't do better than Ω(1)."
• Θ (Big-Theta) — the tight sandwich. When the ceiling and floor are the same shape, the algorithm is Θ(g(n)) — pinned from both sides. This is the strongest, most honest statement you can make.

Linear search makes it concrete. Best case, the song is first in the playlist — one comparison, Ω(1). Worst case, it's last or missing — n comparisons, O(n). The two walls are different shapes, so there is no single Θ for "one run." But averaged over a random position, it does about n/2 comparisons — still Θ(n) on average, because n/2 is just n with a constant we drop. In casual speech everyone says "Big-O" and means "the tight bound," and usually gets away with it. Knowing the three lets you be exact when it counts.

The growth zoo — from cheap to catastrophic

Here is the entire cast, ordered by how fast the cost climbs. Learn this ladder cold; ranking two algorithms is often just "whose class is lower on this list."

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Curves are pretty; the shock is in the numbers. Below is the "how big can n be in one second" table. It uses a measured rate for CPython 3.12 on this machine — a tight Python loop runs roughly 3×10⁷ simple steps per second (I ran it: ~3.17×10⁷, best of five; heavily machine- and language-dependent — compiled C would be 10–100× more). What matters is not the exact rate but the gaps between the rows:

Read the third column slowly. An O(n) algorithm chews through thirty million items a second. Drop to O(n²) and that collapses to about 5,600. Drop to O(2ⁿ) and you're stuck at 25 — one more item doubles the time. At O(n!), ten items is already the edge of the world; eleven items takes eleven times longer than ten. This is why "just brute-force it" quietly stops being an option, and why finding a smarter algorithm can be worth more than a thousand faster machines.

You now hold the map of the whole zoo. The last thing to install isn't a fact — it's a reflex, the one that turns all this into the way you attack a problem you've never seen →

The move: think in growth, hunt the exponent

Everything above collapses into one mental reflex — the move this whole volume is here to install. Faced with any new problem, before you write a line, ask three questions in order:

• What is my n? Name the thing that grows — rows, users, pixels, moves. If nothing grows, complexity is irrelevant and you should just write the clear version.
• What curve am I on? Read the deepest nest. A nested loop over the same data is a quiet O(n²) — fine at n=100, a fire at n=100,000.
• Can I drop to a lower curve? This is the entire game. Sorting first to enable binary search trades O(n²) for O(n log n). A hash table (write it down once, look it up free) turns a repeated O(n) scan into O(1). Remembering answers instead of recomputing them turns exponential recursion linear — you'll see naïve Fibonacci fall from O(2ⁿ) to O(n) that way in a later chapter.

That is the difference the volume's opening promised. The mediocre engineer optimises the constant — a faster loop, a cleverer line. The strong engineer changes the curve, and a curve change beats every constant once n is big enough. It even leaks into ordinary life: you binary-search a bug (does it still break with half the code gone?), you hash instead of re-derive (write down the answer so you never solve it twice), you refuse to re-solve what you already solved. Complexity thinking isn't just for code — it's a way of noticing where effort is being wasted as things scale.

You can now price an algorithm in time. But time is only half the bill — every algorithm also spends memory, and the two trade against each other in ways that decide real systems. Chapter 02 opens the second ledger: space complexity, the stack versus the heap, and why an O(n)-time algorithm can still blow up your RAM →

02Space, and the memory hierarchy — why equal Big-O runs 100× apart

Chapter 1 taught you to price an algorithm in time — operations as n grows. But time is only half the bill. This chapter adds the other half: space — the extra memory a program burns — and then it drops through the abstraction to the metal, where a shocking fact waits. Two algorithms with the identical Big-O can run many times apart in real seconds, and the reason has nothing to do with the exponent on n. By the end you'll be able to read the space cost of any routine, spend memory to buy speed on purpose, and predict when a "slower-looking" layout will crush a "faster" one — because you'll finally see the constant that Big-O throws away.

Space is a bill too — count the extra memory

Space complexity is the same idea as time complexity, pointed at memory: how much extra storage does the algorithm need as a function of the input size n? "Extra" is the key word — we don't count the input itself (it has to exist), we count the scratch space the algorithm allocates on top of it. Two routines that produce the same answer can sit in completely different space classes.

The cleanest split is in-place versus copying. An in-place routine rearranges the data it was given and allocates only a fixed handful of variables — a loop counter, a temp — no matter how big n is. That's O(1) extra space (also called constant space). A copying routine builds a whole new structure the size of the input: O(n) extra space. Watch the exact same "reverse the playlist" idea land in both classes:

import sys
songs = list(range(10000))          # a 10,000-element list

songs.reverse()                     # IN PLACE: swaps ends inward, no new list
# sys.getsizeof before and after: 80056 -> 80056 bytes  (extra: 0)

rev = songs[::-1]                    # SLICE: builds a brand-new 10,000-element list
# sys.getsizeof(rev): 80056 bytes    -> a second full copy, O(n) extra

Line 4, .reverse(), walks two fingers from the ends toward the middle swapping references — the list object's size is byte-for-byte unchanged (we measured 80056 before and after: zero extra). Line 7, [::-1], allocates a second list of the same length — 80056 more bytes that scale with n. Same output, different space class. The built-in pair makes the choice explicit: list.sort() sorts in place and returns None (O(1) extra); sorted() returns a new list (O(n) extra — we measured a 100,000-element sorted() result at 800056 bytes, a full second copy).

So an algorithm has two prices, time and space. The engineer's move is to realise you can pay one to lower the other →

The trade that runs this whole volume: buy time with space

Here is the single most useful sentence in algorithm design: you can almost always trade memory for speed. If a routine keeps recomputing something, store the answer the first time and look it up forever after. If an inner loop keeps searching for a value, build a lookup table so the search becomes an instant jump. You spend O(n) space; you buy back a factor of n in time. This trade is the engine under two techniques you'll meet all volume — hashing (ch6) and memoization (ch9) — and it's worth seeing raw, right now.

Take two-sum: is there a pair in a list that adds to a target? The brute force tries every pair — two nested loops, ~n²/2 checks, and O(1) extra space. The trade: keep a dict of numbers you've already seen; for each new number just ask "is target − x in there?" — an O(1) question. One pass, O(n) time, O(n) space. We ran both on n = 20,000 with a target that has no answer (so both must look at everything — the honest worst case):

def brute(nums, target):            # O(1) space, O(n^2) time
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def hashed(nums, target):           # O(n) space, O(n) time
    seen = {}                       # <-- the memory we BUY
    for i, x in enumerate(nums):
        if target - x in seen:      # an O(1) question, not an O(n) scan
            return (seen[target - x], i)
        seen[x] = i
    return None

The brute version's inner loop (lines 3–5) restarts a full scan for every element — that's where the n² comes from. The hashed version replaces "scan for the complement" with the in seen test on line 11, and seen is the price: a dict that grows to n entries. The payoff was not subtle. On our machine (timings are hardware-dependent), the brute force took ≈8,793 ms; the hashed version took ≈2.0 ms — about a 4,300× speedup — in exchange for a dict of ~590 KB. You handed the machine half a megabyte and it handed back nearly four-thousandfold. Here is that trade as a curve — every unit of memory you spend buys back a chunk of time:

Buying time with space assumes memory is one flat, uniform thing you simply "have." It isn't. Memory is a hierarchy, and that changes everything →

Not all memory is one place — the hierarchy

Volume 1 drew RAM as one long row of numbered boxes. True — but it hid a secret the CPU spends enormous effort on: reaching those boxes is slow. A modern processor executes an instruction in a fraction of a nanosecond, but a trip out to main memory (DRAM) costs it roughly 100 ns — during which the core could have run hundreds of instructions. So chip designers stack a pyramid of progressively smaller, faster memories in front of RAM, each a cache — a small store of recently-used data kept close to the core. From fastest and tiniest to slowest and vastest: registers → L1 → L2 → L3 → RAM → SSD → disk.

The latencies span a range that's hard to believe. These are typical order-of-magnitude figures for a modern machine (not measured on yours — real numbers vary by hardware), scaled into human time so you can feel them. If an L1 hit were one second:

Read that pyramid again, because it reframes performance entirely. The CPU is a Formula-1 engine bolted to a supply chain. If the part it needs is in a register or L1, it's already in its hand. If it has to fall to RAM, it stalls for the human equivalent of a coffee break. Fall to disk, and it's waiting months. The whole game of fast code is keeping the data the CPU wants near the top of this pyramid — and the CPU can't do that alone. It guesses, using one simple bet.

A 64-byte line, fetched on every miss, quietly holding eight of your neighbours. That single fact is why two O(n) loops can finish an order of magnitude apart →

Two O(n) loops, one many times slower — the access pattern decides

Now the payoff. Big-O counts operations and treats every memory access as one unit of cost. The hardware does not. An access that hits cache is roughly 100× cheaper than one that misses to RAM. So two algorithms that do the exact same number of accesses — same Big-O — can run wildly apart if one touches memory in an order the caches love and the other in an order they hate. The hidden multiplier Big-O drops on the floor, the constant factor, is set by the memory access pattern.

Picture two ways to hold a million numbers. A contiguous array lays them end to end in one block. Walk it front to back and every 64-byte cache line you pull delivers eight useful int64s in a row — one miss, then seven free hits — and the prefetcher, seeing your straight march, has the next line ready. Now a linked list: each number lives in its own little node, allocated whenever, scattered across the heap, each pointing to the next. Walk it and every node.next is a jump to an unrelated address — a fresh cache miss per node, seven-eighths of every fetched line wasted, the prefetcher blind because there's no pattern to predict. Same n steps. Same O(n). Utterly different metal.

We didn't just assert this — we timed it. First, the same math in two layouts: sum ten million integers as a Python list (a block of references pointing off to separately-boxed int objects) versus a NumPy array (the raw int64s packed contiguously). Same additions, same O(n):

import numpy as np
lst = list(range(10_000_000))          # 10M ints; Python list of references
arr = np.arange(10_000_000)            # 10M ints; contiguous int64 block

sum(lst)      # measured best: ~35.4 ms
arr.sum()     # measured best: ~ 4.1 ms   -> ~8.6x faster, same O(n)

Same operation count; ~8.6× apart (hardware-dependent), because the array is a tight contiguous block the caches and prefetcher love, while the list scatters its int objects across the heap — pointer-chasing, a miss risk per element. And the array is smaller too: we measured the list of ten million ints at ~360 MB (8-byte references plus a ~28-byte boxed int each) versus ~80 MB for the NumPy array — 4.5× less memory and faster. To prove the effect is the access order and nothing else, we then walked the identical data twice — once in sequential order, once through a random permutation (same reads, only the pattern differs). Through NumPy's C loop over a 320 MB block, random order ran ~4.6× slower; a pointer-chase through Python's interpreter (which dilutes the effect with its own overhead) still ran ~2.3× slower. The exponent on n never changed. Only the cache did.

You've now seen the two hidden costs Big-O ignores: extra space, and the constant set by locality. The last move is to turn that into a habit →

The 1% move: respect the constant, spend space on purpose

Chapter 1 gave you the lens to choose the lower growth curve. This chapter installs the reflex that separates engineers who "know Big-O" from those who ship fast systems: Big-O is where you start, not where you stop. Once you've picked the right complexity class, two more questions decide real speed — and most people never ask them.

Question one: what will this cost in space, and can I trade it? When something is slow because it recomputes or re-scans, ask what you could store to make the repeat instant. That's the hashing/memoization move (ch6, ch9) — and now you know its price is real memory, drawn from a finite budget, so you spend it deliberately, not reflexively. Question two: how will the data be laid out, and how will I walk it? Two designs with the same Big-O are not equal; the one that marches contiguously through memory, feeds the prefetcher, and keeps its hot data in cache will win. This is machine sympathy — writing code that flows the way the hardware wants to run.

The everyday transfer is real. "Buy time with space" is just writing it down: you don't re-derive a friend's phone number every time — you stored it once for O(1) recall. "Respect locality" is keeping what you're using within reach — the tools on the bench, not out in the garage. And the master habit is the one to carry into every problem for the rest of this volume: after you've found the right complexity, ask "what am I storing, and how am I walking it?" — because that question is the difference between code that looks fast on paper and code that is fast on the metal.

That paradox — an operation that's occasionally expensive yet genuinely cheap on average — is the whole of Chapter 3: amortized analysis, the honest accounting that explains why a million appends stay flat despite the resize spikes. →

03Amortized analysis — the honest average

Chapter 1 gave you one number for an algorithm's cost. But most algorithms don't have one cost — they have a best day, a worst day, and a typical day, and the gap between them can be the gap between "instant" and "the site is down." This chapter teaches you to price all three, and then a subtler idea that trips up almost everyone: how a single operation can be wildly expensive and yet be genuinely cheap. After it, you'll be able to look at list.append — an operation that occasionally copies your entire list — and prove, with a stopwatch and a derivation, that it costs a constant. That proof is called amortized analysis, and it is one of the most useful ways of thinking an engineer owns.

One algorithm, three honest questions

Take the simplest search there is: walk a list left to right, comparing each item to your target, and stop when you find it (you stepped this in trace T22). How many comparisons does it cost? The honest answer is it depends on where the target sits — so we ask three separate questions, and each has a precise meaning.

• Best case — the luckiest input. The target is in slot 0; you find it in 1 comparison. Cost that never gets beaten: O(1).
• Worst case — the unluckiest input. The target is in the last slot, or absent entirely; you check all n items. Cost that is never exceeded: O(n).
• Average case — the expected cost over a distribution of inputs. If the target is equally likely to be anywhere, you scan n/2 items on average — still O(n), but with a hidden factor of one-half.

These are three different measurements of the same code — nothing about the algorithm changed, only the input did. Best case is a fact about luck and rarely worth designing around. Average case needs an assumption about which inputs show up, and that assumption can be wrong. Worst case needs no assumptions at all — it is a promise: "no matter what you throw at me, I will not cost more than this." That is why, when an engineer says an algorithm "is O(n)" with no qualifier, they almost always mean the worst case. It's the only one you can hand a stranger.

Fine for a toy search. But does the gap between "typical" and "worst" ever actually change which algorithm you'd pick? Oh, it decides careers. →

Why the case you measure decides the algorithm you choose

Here is where this stops being bookkeeping. Quicksort (stepped in trace T28) is, on typical data, one of the fastest sorts ever written: on random input it does about n·log₂n comparisons. But its speed comes from a gamble — it picks a pivot and splits the list around it, hoping for two roughly equal halves. Feed it an input that always splits into "one item" and "everything else," and every split does real work while the problem barely shrinks: the cost collapses to O(n²). And the input that triggers this? For the textbook "pivot = last element" version, it's an already-sorted list — the most innocent-looking data imaginable. Let's not take that on faith; let's count the comparisons.

def quicksort_count(a):
    comps = 0
    def qs(lo, hi):
        nonlocal comps
        if lo >= hi: return
        pivot = a[hi]                 # naive: last element is the pivot
        i = lo
        for j in range(lo, hi):
            comps += 1                # count every key comparison
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        qs(lo, i-1); qs(i+1, hi)
    qs(0, len(a)-1)
    return comps

# n = 2000
# random input : 25,335 comparisons    (~ n·log2 n = 21,932)
# sorted input : 1,999,000 comparisons (~ n^2 / 2  = 2,000,000)   -> 79x worse

Line by line: comps tallies each comparison. qs partitions the slice a[lo..hi] around pivot, sweeping j across it and counting one comparison per step, then recurses on the two sides. On 2,000 random numbers it spent 25,335 comparisons — right in the n·log n neighbourhood. On the same 2,000 numbers already sorted, it spent 1,999,000 — which is exactly 2000·1999/2, the sum 1 + 2 + … + 1999, the fingerprint of a fully lopsided split every single time. Same algorithm, same n, 79× more work — because the case changed.

Now the mirror image, and the reason your dict and set feel like magic. A hash lookup is O(1) on average — it jumps straight to a bucket (Volume 1, chapter 7). Its worst case, when every key collides into one bucket, degrades to an O(n) scan. Usually that worst case is a fairy tale you never meet — but you can force it, and watch O(1) rot into O(n) in real time:

class Bad:
    def __hash__(self): return 0     # EVERY key lands in the same bucket
    def __eq__(self, o): return self.v == o.v

# average nanoseconds per membership test ("x in the_set"):
# size 1000:  normal set     72 ns      colliding set    69,024 ns
# size 2000:  normal set     72 ns      colliding set   113,662 ns
# size 4000:  normal set     74 ns      colliding set   354,515 ns

Read the two columns. The normal set answers in ~72 nanoseconds whether it holds a thousand items or four thousand — flat, the signature of O(1). The sabotaged set, where every key hashes to 0, gets steadily slower as it grows — the signature of O(n). (Timings are from this laptop; the shape, not the exact digits, is the point.) This isn't academic: feeding a web server keys crafted to collide is a real denial-of-service attack called hash flooding, which is exactly why modern languages randomize their hash seed at startup.

Amortized: cheap over a lifetime, not by luck

They're not wrong — they're using a third kind of accounting, and it's the star of this chapter. Amortized cost is the total cost of a whole sequence of operations, divided by the number of operations. The word comes from finance — to amortize a cost is to spread a big one-time expense across many periods so each period carries a small, even share. A £1,200 annual subscription isn't "£1,200 expensive"; amortized over the year it's £100 a month. The £1,200 charge is real, but no single month feels it.

The magic move is this: some operations are occasionally expensive but usually trivial, and the expensive ones are rare enough that when you add up the whole bill and divide, the average is small — often a constant. When we can prove that, we say the operation is O(1) amortized. And here is the part that makes it powerful rather than hand-wavy: this is still a worst-case statement. It doesn't say "append is usually fast." It says "any sequence of m appends costs at most c·m total — guaranteed, for every possible sequence." No luck, no distribution, no coin flips. A promise.

Abstract enough. Let's pin it to the one operation you've typed ten thousand times — and finally cash the promissory note chapter 1 wrote when it said "append is O(1)." →

The canonical case: why append is O(1) amortized

You met the machinery in Volume 1, chapter 6, so we'll use it, not rebuild it. A Python list is a dynamic array: a contiguous block of 8-byte reference slots, deliberately over-allocated with a few spare seats at the end. append normally just drops one reference into the next spare seat — one write, cost O(1), no matter how long the list is. But when the spare seats run out, there's no room to grow in place (the neighbouring memory is taken). So CPython rents a bigger block elsewhere, copies every existing reference across, frees the old block, and then writes your new item. That copy touches all n references: cost O(n). Watch the spare seats refill with sys.getsizeof, which reports the container's own byte size:

import sys
lst = []
for i in range(1, 33):
    lst.append(i)
    # container bytes jump ONLY at len 1, 5, 9, 17, 25 …
# capacity sequence as it grows one at a time:
#   4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128 …

The bytes don't climb smoothly — they jump, then hold flat for several appends, then jump again. Each jump is a relocation (an O(n) copy); each flat stretch is a run of cheap O(1) appends landing in spare seats. The relocations get rarer as the list grows, because each new block is proportionally bigger than the last. That "rare, and rarer over time" is the whole trick — and it's exactly the tall-red-bar-among-green picture from a moment ago. This is the concrete shape of a per-operation cost that is mostly constant with occasional spikes. Turn the knob and feel it:

Drag n and notice the two things happening at once. The red spikes get taller — a resize at length 32 copies 32 references, at length 64 copies 64. Yet the amber average line refuses to climb with n; it just wobbles in a tight band around 2 — nudged up the instant a resize lands, then settling back as the next run of cheap appends dilutes the cost. Rising spikes, bounded average. That contradiction — the individual worst case grows without bound while the per-operation average stays pinned inside a constant band — is amortized analysis in one picture. The next section proves why the line can't rise.

Two nagging questions remain. Why is the average exactly 2 and not creeping upward forever? And what does the real, non-doubling CPython actually cost? Time to add up the whole bill. →

The aggregate method: add up the whole bill, then divide

The cleanest way to prove an amortized bound is the aggregate method: compute the total cost of a sequence of operations, then divide by how many there were. No per-operation cleverness — just one big sum. Take m appends into a list that doubles when full. The cheap part is easy: every append does exactly one write, so that's m writes total. The expensive part is all the copying at resizes. With doubling, resizes happen at lengths 1, 2, 4, 8, …, up to m, and each copies the block it's leaving — so the copies are 1 + 2 + 4 + 8 + … up to roughly m.

That sum is the punchline. A doubling geometric series always adds up to less than twice its largest term: 1 + 2 + 4 + … + m < 2m. So all the copying across the entire sequence costs under 2m, and the writes cost m — a grand total under 3m for m appends. Divide by m: under 3 per append, a constant. The list can grow to a billion; the average never budges. That is the derivation behind "append is O(1) amortized."

Enough theory — let's put a real stopwatch on a real million appends and check the promise against CPython, spares, non-doubling growth and all:

import time
N = 1_000_000
lst = []
t0 = time.perf_counter()
for i in range(N):
    lst.append(i)
print((time.perf_counter() - t0) * 1000, "ms")   # ~= 55 ms  -> ~55 ns / append

# counting the ACTUAL relocations over the same run:
#   resizes            : 86
#   total slots copied : 8,445,096   ->  8.4 copies per append
#   writes per append  : ~9.4        (constant - does NOT grow with N)

A million appends finished in about 55 milliseconds — roughly 55 nanoseconds each (this laptop; yours will vary). For comparison, writing into a list that's already the right size — pure O(1) writes, zero growth — clocked ~50 ns each. So all of CPython's growing, relocating, and freeing added only about 5 ns per append on average. The counters explain why: across a million appends there were only 86 relocations, and the total copying came to ~8.4 slot-copies per append. That's the honest CPython constant — about 9 writes per append, not the model's 2, because CPython grows by ~1/8 rather than doubling. Smaller growth means more frequent resizes means a bigger constant. But constant it is: independent of N, exactly as promised. The doubling model told the right story; the machine just uses a different constant.

The trap: amortized is not average-case

This is the distinction that separates people who've memorized the words from people who understand them — and the myth is worth killing out loud.

Line them up. Quicksort's average O(n log n) is a statement about a distribution of inputs: "if your input is random, expect n log n." Hand it a sorted array and the promise evaporates — you get n². The good behaviour was conditional on luck. Now append's amortized O(1): there is no "if your appends are random." Every sequence of a million appends costs about 9 million writes — the sorted case, the adversarial case, the you-chose-the-inputs-to-hurt-me case, all identical. You cannot construct a bad sequence, because the guarantee is over the sum, not over a typical draw. Average-case can be defeated by a clever enemy; amortized cannot.

You can now price an algorithm three honest ways and prove a spiky operation is secretly cheap. But pricing is diagnosis, not cure. Next: the design loop itself — start with brute force, then ask the one question that turns a coder into an engineer, "where is the wasted work?" — and watch an O(n²) two-sum collapse to O(n) before your eyes. →

04Brute force, then spot the waste

Chapters 0–3 gave you the yardstick: count operations, watch them grow, respect the constant. This chapter gives you the method — a five-step loop you run on any problem, from an interview whiteboard to a production incident. By the end you'll have a reflex that fires before you write a single clever line: solve it the dumb way, find the wasted work, delete it, re-check the cost. That loop is the spine of every remaining chapter, and it is the actual difference between someone who codes and someone who engineers.

Start with brute force. It is step one, not shame.

Brute force means: try every possibility and check each one. It has a bad reputation it does not deserve. Brute force is where every hard problem starts, because it does two irreplaceable jobs. First, it pins down what "correct" even means — you cannot optimize an answer you can't yet produce. Second, it hands you a baseline complexity: the number to beat. Skip it and you're optimizing in the dark.

Take the problem we'll ride all chapter — two-sum. Given a list of numbers and a target, find two of them that add up to the target. Concretely: your playlist has tracks of length [200, 90, 150, 60] seconds, and you want two that exactly fill a 240-second (4:00) slot. The brute-force reading is literal: look at every pair and test its sum. How many pairs are there? Pick the first element (n choices), pick a different second (n−1 choices), and since the pair (i, j) is the same as (j, i), divide by two. That's n(n−1)/2 pairs — a number we counted, not looked up. For n = 4 that's exactly 6 pairs.

def two_sum_brute(nums, target):
    n = len(nums)
    for a in range(n):                       # pick the first element
        for b in range(a + 1, n):            # pick a LATER second element
            if nums[a] + nums[b] == target:  # test this pair's sum
                return (a, b)                # done the instant we find one
    return None                              # no pair adds up

Read it as the picture: the outer loop picks a, the inner loop picks every b to its right (that's the a + 1 — it's why we only fill the triangle, never re-checking a pair), and the if tests the one thing we care about. It is obviously, boringly correct. That is its whole value right now. Ship the boring version first; you now have a truth you can measure and a truth you can test against.

We have a correct answer. But "correct" isn't "good." How expensive is this, really — and where does it hurt? →

Measure the baseline — count, then feel the growth

Deriving the cost is just reading the loops (the skill from chapter 1): the inner body runs once per pair, so the operation count is n(n−1)/2. Drop the constant and the lower term and it's O(n²). But a formula is abstract — let's make the growth land in your gut by running it. I counted the exact inner-loop checks in the worst case (no pair exists, so it scans everything):

Every 10× more input is 100× more work — that's the signature of squaring. The same signature shows up on the clock. I timed the real function (worst case, on this laptop — your absolute numbers will differ, the shape will not):

Now the trap that ends careers quietly. At n = 1,000 this brute force finishes in ~19 ms — instant, ships, "works on my laptop." Push it to a million items and the squared growth means about 250,000× the work of n=2,000: extrapolated from the measured times, roughly 5.5 hours for one call. The demo was fine. Production is on fire. Nothing changed but n.

So the baseline is quadratic and it will detonate. Good — now the single most valuable question in all of engineering. →

The one question: where is the wasted work?

Here is the mental move that turns a coder into an engineer. You look at the brute force and ask: where am I doing work I've already done, or don't need to do? Wasted work hides in three shapes, and you learn to smell all three:

• Recomputing — calculating the same value over and over (you'll kill this with memoization / dynamic programming in chapter 9).
• Re-scanning — sweeping through data you already looked at (killed with hashing, ch6, and two-pointers, ch7).
• Ignoring structure — the data is sorted, or bounded, or monotonic, and you're not exploiting it (killed with binary search, ch12, and more).

Point the question at two-sum. For each element x, brute force computes what it needs (need = target − x) and then re-scans the whole rest of the list hunting for that number. But look at what the scan is searching through: numbers we already walked past. We had them in our hands one step ago and we threw them away, so now we walk the list again, and again, and again. The wasted work is the re-scan. The inner loop is a search for a value we've already seen.

How much work is actually wasted? Slide it and see. The brute force does n(n−1)/2 comparisons; a solution that looked at each element just once would do n. The gap between those two bars is the redundant work — and it's almost the entire bar.

That question is the whole solution. The fix is the most human idea in computing: write it down. →

Kill it with a technique — remember what you've seen

When you keep re-searching for something, you stop searching and start remembering. In code, "remember, and look up instantly" is a dict — the hash table from Volume 1 that answers "is X in here, and where?" in roughly one step, O(1), no matter how full it gets. (That's a whole technique; chapter 6 is devoted to it.) So we walk the list once. At each element x we ask the dict a single question — "have I already seen target − x?" — and if not, we drop x into the dict and move on. The inner scan doesn't get faster; it disappears.

def two_sum_fast(nums, target):
    seen = {}                        # value -> the index we saw it at
    for i, x in enumerate(nums):     # ONE pass, no inner loop
        need = target - x            # the partner that would complete the pair
        if need in seen:             # already met it? O(1) dict lookup
            return (seen[need], i)   # found the pair
        seen[x] = i                  # otherwise, remember x for later
    return None

Line by line: seen is the memory — a value mapped to where we found it. The single loop takes each x in turn. need is the number that would complete the pair. need in seen is the move: instead of re-scanning, we ask the dict, and it answers in one hop. If the partner is there, we're done; if not, we record x so a future element can find us. Every past element is already written down, so no element ever gets looked at twice. Run it on the playlist and watch the memory fill until it pays off:

i=0 x=200 need=40  40 in seen? no   -> remember  seen={200:0}
i=1 x=90  need=150 150 in seen? no  -> remember  seen={200:0, 90:1}
i=2 x=150 need=90  90 in seen? YES  -> return (1, 2)     # 90 + 150 = 240

Three steps and it stops. Step 0 remembers 200. Step 1 remembers 90. Step 2 needs 90 — and 90 is already written down, at index 1 — so it returns instantly. The list of 90 and 150 was never scanned twice; the dict just recognized the partner the moment it walked by. Step it in full in trace T31.

The re-scan is gone and the answer's still correct. But "feels faster" is a feeling. Prove it. →

Re-check the complexity — did it actually get better?

Never trust a "faster" version until you've re-derived its cost — clever code fools people constantly. So count again. The fast version has one loop over n elements. Each iteration does a fixed amount of work: one subtraction, one dict lookup, maybe one dict insert — all O(1) on average (Volume 1's hash table). One times n is O(n). We traded n(n−1)/2 for n. Not a shave — a change of curve, from the exploding red to the gentle blue.

And because it's a curve change, the win doesn't just exist — it grows with n. I measured both versions on the same inputs (worst case, this laptop; treat the exact milliseconds as approximate):

Look at that speedup column climbing. It isn't a fixed "10× faster" — the multiplier itself doubles as n doubles, because O(n²) vs O(n) means the ratio is n/2. That million-element call that would've taken ~5.5 hours by brute force? The hash version finishes it in well under a tenth of a second. Same laptop, same problem, different curve. Turn the knob below and watch the wall-clock cross from milliseconds into years:

There's an honest cost, and a 1% engineer names it out loud: the dict holds up to n entries, so we spent O(n) extra memory to buy O(n) time. That's the space–time tradeoff (ch2) — hashing and memoization both pay memory to delete work. Almost always worth it. Not free.

Two-sum was one problem. But that sequence — dumb, measure, spot, delete, re-check — wasn't about two-sum at all. It's the loop. →

The loop is the whole game

Step back and name what we just did, because you'll do it in every chapter from here on. It's a five-step cycle, and it never changes:

That's it. That's the operating system. And notice: the rest of Volume 3 is just a toolbox for step 4. Divide & conquer (ch5), hashing (ch6), two pointers and sliding windows (ch7), greedy (ch8), dynamic programming (ch9), backtracking (ch10) — each one is a specific way to delete a specific kind of waste. You don't memorize which to use; you find the waste, and the technique that kills that waste is the one you reach for. Steps 2 and 5 — count the operations — are the same skill from chapters 0 and 1, and they're what keep you from lying to yourself. Play the whole loop live in the Algorithms Lab.

The transfer out of code is real and it's daily. Binary-search your debugging: don't read all 400 commits, bisect them. Hash your memory: don't re-derive a phone number every time, write it down for instant recall. Greedy your errands: nearest stop first. Don't re-solve what you've solved. The loop — "what am I doing over and over that I could do once?" — is a way of seeing, and it works on spreadsheets, supply chains, and your own calendar.

for _ in range(200_000):                      # throw random cases at both
    nums = [randint(-20, 20) for _ in range(randint(0, 8))]
    target = randint(-40, 40)
    assert (brute(nums, target) is None) == (fast(nums, target) is None)   # oracle: both agree WHETHER a pair exists (the two may pick different valid indices)
# ran clean: 0 mismatches

Step 4 needs techniques. The first and most powerful one is a single idea: what if, instead of one big problem, you had two half-sized ones — and each of those split again? Chapter 5 is the power of halving. →

05Divide & conquer — the power of halving

Here is a superpower hiding in one sentence: if you can cut a problem cleanly in half, you can solve a version a thousand times bigger for the price of ten more steps. This chapter takes that idea apart to the studs. You will learn the three-line template every divide-and-conquer algorithm shares, derive — not memorise — why halving gives you log n depth, read a recurrence like a sentence, and meet two genuine marvels: raising a number to the millionth power in twenty-five multiplications, and multiplying two 300,000-digit numbers faster than the schoolbook method any human was ever taught. By the end you will reach for "can I split this?" the way a locksmith reaches for a pick.

Split, solve, stitch — the three-line template

Every divide-and-conquer algorithm is the same three moves wearing different clothes. Divide: break the input into smaller pieces of the same shape as the original. Conquer: solve each piece — and because a piece is just a smaller version of the whole problem, you solve it by calling the very same procedure (that is recursion, from Volume 1: a function that calls itself, each call a fresh frame on the stack). Combine: stitch the sub-answers into the answer for the whole. The art is almost never in the split; it is in the combine. Get the stitch right and the recursion does the rest for free.

Merge sort is the cleanest example alive. To sort a list: split it into two halves, sort each half (by calling merge sort on it), then merge the two sorted halves into one sorted list by repeatedly taking the smaller of the two front elements. The split is trivial — cut the list in the middle. The genius is the merge: two already-sorted lists fuse into one in a single walk down both. We step this line by line in trace T30 — here we care about the shape, not the mechanics.

def merge_sort(a):
    if len(a) <= 1:                 # a list of 0 or 1 is already sorted — the base case
        return a
    mid   = len(a) // 2             # DIVIDE: split point, right in the middle
    left  = merge_sort(a[:mid])     # CONQUER: sort the left half (same function, smaller input)
    right = merge_sort(a[mid:])     # CONQUER: sort the right half
    return merge(left, right)       # COMBINE: fuse two sorted halves into one

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):   # walk both, always take the smaller front
        if x[i] <= y[j]: out.append(x[i]); i += 1
        else:            out.append(y[j]); j += 1
    return out + x[i:] + y[j:]         # one side is exhausted; append the rest

Read the top function as English: a one-element list is done; otherwise split, sort both sides, merge. The if len(a) <= 1 line is the base case — the floor where recursion stops instead of splitting forever. The left and right lines are the two recursive descents. The merge helper is the whole payoff: because both inputs are already sorted, comparing only the two front elements is enough to know which value comes next globally. I ran this on random lists from 1 to 100,000 elements; every output came back in perfect ascending order, and the number of comparisons tracked n·log₂n closely (100,000 items → 1,536,134 comparisons, against n·log₂n ≈ 1,660,964).

The split gives you a tree. How tall is that tree — and why does its height decide everything? →

Why halving buys you log n

Start with a search space of one billion items and keep throwing away half. A billion → 500 million → 250 million → … how many throws until one item is left? Not a billion. Not a thousand. Thirty. That number — how many times you can halve n before you hit 1 — is the definition of log₂ n, the base-2 logarithm. It is the exact inverse of doubling: doubling asks "start at 1, how many doublings to reach n?"; halving asks the same question backwards. I checked the whole ladder in Python: n = 1,000,000 takes 20 halvings, 1,000,000,000 takes 30, and 8,000,000,000 — every human alive — takes just 33.

import math
for n in [1_000, 1_000_000, 1_000_000_000, 8_000_000_000]:
    print(n, "halvings to reach 1:", math.ceil(math.log2(n)))
# 1000 -> 10 · 1_000_000 -> 20 · 1_000_000_000 -> 30 · 8_000_000_000 -> 33

This is exactly why binary search (stepped in trace T23) finds any name in a sorted phone book of eight billion in 33 comparisons: each comparison discards half the remaining names. And it is why merge sort's tree is only log₂ n levels deep — every level halves the piece size, so after log₂ n halvings the pieces are single elements. A million-element merge sort is a tree just 20 levels tall. Depth is logarithmic because halving is the inverse of doubling; everything else in this chapter is a consequence of that one fact.

Turn the knob yourself. Push n up by a factor of a thousand and watch the recursion depth crawl up by ten — the number that would make a linear algorithm choke doesn't even make the tree taller.

So the tree is log n tall. But each level does some work too. How do the two multiply into a total? →

Reading the recurrence: T(n) = a·T(n/b) + f(n)

The running time of any divide-and-conquer algorithm is captured by one line, the recurrence. Read it as a sentence. T(n) is "the time to solve size n." It equals a — the number of pieces you recurse into — times T(n/b) — the time for one piece, which is 1/b the size — plus f(n), the work you do yourself at this level to split and combine. For merge sort: you make a = 2 recursive calls, each on a half so b = 2, and the merge scans all n elements so f(n) = n. That is T(n) = 2·T(n/2) + n.

You can solve it by pure counting, no theorem required. Draw the tree. The top level does n units of merge work. It has two children, each doing n/2 — together n again. Their four grandchildren each do n/4 — together n once more. Every level sums to n, because the pieces shrink by exactly the factor that they multiply in number. And how many levels are there? From the last section: log₂ n. So the total is n per level times log₂ n levels — n·log₂ n. You just derived merge sort's complexity by adding up a tree.

The Master Theorem is just this counting argument, generalised, boiled down to a three-way comparison you can do in your head. It pits the work you do at the top (f(n)) against the work piling up in the leaves (which grows like n^(log_b a)). Whichever side is bigger wins the total:

• Leaves win (many small pieces, cheap combine): the answer is dominated by the bottom of the tree — total ≈ n^(log_b a).
• It's a tie (both sides balanced — merge sort's case): every level contributes equally, so you pay the per-level work times the log n levels — total ≈ f(n)·log n.
• The top wins (expensive combine, few pieces): the very first level dominates and the recursion is a rounding error — total ≈ f(n).

That is the whole theorem in plain words: compare the splitting/combining work to the work waiting in the subproblems; the bigger one sets the price. You almost never need the formal version — but here it is for when you do.

Watch the tie happen. Slide n and see every level of the tree carry the same total load, with the number of levels — and so the total — following n log₂ n, while the quadratic method it beats balloons out of frame.

Fast exponentiation — xn in log n multiplications

Here is the marvel. To compute xn the obvious way you multiply x by itself n−1 times: 2¹⁰⁰⁰⁰⁰⁰ would be 999,999 multiplications. But multiplication lets you double the exponent with a single squaring: x² squared is x⁴, squared again is x⁸, then x¹⁶… each squaring doubles the exponent instead of adding one to it. And doubling, we now know cold, reaches any target in log₂ n steps. So build the exponent up in powers of two, and multiply in the pieces the binary form of n tells you to keep.

That is exponentiation by squaring. Write n in binary; walk its bits from the top; square the running result at every bit, and multiply in an extra x whenever the bit is 1. The multiplication count is (bit_length − 1) squarings plus (popcount − 1) extra multiplies, where popcount is the number of 1-bits. I ran the counter:

def fast_pow(x, n):
    result = 1
    for bit in bin(n)[2:]:      # binary digits of n, most-significant first
        result = result * result        # SQUARE — doubles the exponent so far
        if bit == '1':
            result = result * x          # MULTIPLY — add one to the exponent
    return result

# verified against Python's own x**n on 2000 random cases: all equal.
# 2 ** 1_000_000:  bin(n) has 20 bits, 7 of them are 1
#   -> 20 squarings + 7 multiplies = 27 executed (the leading 1*1 square and 1*x multiply are trivial, so 19+6 = 25 do the real work)
#   the naive loop would need 999,999.

Line by line: result starts at 1. For each binary digit of n from the most significant down, we square result — that doubles the exponent we have accumulated so far — and if the current bit is a 1 we do one extra multiply by x, nudging the exponent up by one to match that bit. Because 1000000 is binary 11110100001001000000 (20 bits, 7 ones), the machine needs 19 squarings + 6 multiplies = 25 multiplications to produce a number with 301,030 decimal digits. Twenty-five, not a million. I verified fast_pow against Python's built-in x**n on 2,000 random inputs — every result matched (and Python's own integer ** uses exactly this trick internally).

Turn the exponent yourself. Watch the binary of n decide which steps are squares and which add a multiply, and watch the fast count sit near log₂ n while the naive count runs off to n.

Squaring made powers cheap by halving the exponent. Could the same halving instinct make plain old multiplication of giant numbers cheaper than the method you learned in school? →

Karatsuba — multiplying giants below n²

The multiplication you learned as a child is O(n²): to multiply two n-digit numbers, every digit of one meets every digit of the other — n × n little products. Double the digit count and the work quadruples. For the 300,000-digit numbers that 2¹⁰⁰⁰⁰⁰⁰ produces, that quadratic cost is brutal. For a long time it was widely assumed that n² was simply the price of multiplication. In 1960, following a question the mathematician Andrey Kolmogorov had posed, a young student named Anatoly Karatsuba found a method that beat it — and the surprise reshaped how people thought about the limits of arithmetic.

The trick is divide and conquer with one stroke of genius. Split each n-digit number into a high half and a low half: x = a·10^(n/2) + b, y = c·10^(n/2) + d. The schoolbook product needs the four cross-products ac, ad, bc, bd — that is 4·T(n/2), and four is too many: it gives back n². Karatsuba noticed that the middle term ad + bc can be recovered from products you already need plus one more, because (a+b)(c+d) = ac + ad + bc + bd, so ad + bc = (a+b)(c+d) − ac − bd. That means three multiplications suffice instead of four: ac, bd, and (a+b)(c+d). One saved multiplication, taken recursively at every level, changes the exponent itself.

Why does dropping 4 to 3 change the exponent? Straight from the recurrence. Schoolbook is T(n) = 4·T(n/2) + n; Karatsuba is T(n) = 3·T(n/2) + n. By the watershed rule, the leaf work grows as n^(log₂ a): log₂4 = 2 gives n²; log₂3 ≈ 1.585 gives n^1.585. A single fewer branch per node, compounded over log n levels, bends the whole curve. This is not folklore — Python's own big integers use it. CPython multiplies small integers the schoolbook way but switches to Karatsuba once the numbers pass a threshold. I timed multiplication of random numbers as their size doubled:

import random, time
def t(bits, reps):
    a, b = random.getrandbits(bits), random.getrandbits(bits)
    a * b                                   # warm up
    s = time.perf_counter()
    for _ in range(reps): a * b
    return (time.perf_counter() - s) / reps

#  bits     time/mult     ratio when bits double   (schoolbook would be 4.0x)
#  64000    8.2e-4 s
# 128000    2.4e-3 s      2.92x      implied exponent log2(2.92) ~ 1.55
# 256000    7.5e-3 s      3.05x      implied exponent log2(3.05) ~ 1.61

Read the ratios. Every time the numbers doubled in length, the time grew by about 3×, not the 4× that schoolbook n² demands. Take log₂ of that measured ratio and you get roughly 1.58 — landing right on Karatsuba's theoretical log₂3 = 1.585. (These are wall-clock timings on this machine; the exact milliseconds will differ on yours, but the ratio — the slope — is a property of the algorithm, not the hardware.) You are watching a 1960 theorem tick inside your interpreter every time you multiply large integers.

Splitting bought us logarithmic depth, cheap powers, sub-quadratic products. But there's one more prize hiding in the word independent — and it's about the metal. →

The metal, and the mental move

Look back at the merge-sort tree. The left half and the right half never touch until the merge. They are independent — nothing the left recursion computes changes anything the right one does. That independence is a gift to the hardware. In Volume 1 you met the modern reality that a CPU has many cores. Independent subproblems can be handed to different cores at the same time: sort the left half on core 0 while core 1 sorts the right, then merge. Divide and conquer is the most natural way there is to write parallel code, because the algorithm has already carved the work into pieces that don't interfere. This is not a metaphor — it is the shape of MapReduce, the pattern that let Google process the whole web across thousands of machines: split the data, solve the shards in parallel, combine. Divide and conquer at datacenter scale.

There is a cache dividend too, from Volume 1's memory hierarchy. When a subproblem shrinks enough to fit entirely in fast cache, every remaining operation on it runs at cache speed instead of paying for trips to main memory. Recursion naturally drives the working set down to that sweet spot — which is why cache-aware divide-and-conquer sorts and matrix multiplications routinely beat "flat" algorithms with the identical Big-O. Same curve on paper; the one whose data sits in cache wins the wall clock. (This is the recurring lesson of the whole volume: at equal Big-O, constants and data layout decide the race.)

Now the mental move — the thing to carry out of this chapter into problems that have nothing to do with sorting. When you face an unknown, ask what single question cuts the space of possibilities in half. A bug appears somewhere in 2,000 lines of new code: don't read line 1 and creep forward — comment out half, see which half misbehaves, repeat. Eleven steps, not two thousand. (This is literally what git bisect does: it binary-searches your commit history for the one commit that broke the build, in log₂ of your commits.) A number is somewhere between 1 and a million and you get hot/cold hints: guess the middle every time and you corner it in twenty guesses. A wide spreadsheet has one wrong total: split it, sum each half, chase the half that's off. Halving is not a sorting technique. It is a way of attacking uncertainty — and once you see it, you will see it everywhere.

Next chapter turns from splitting to a different instinct entirely: hashing — how spending a little memory lets a dict answer "is this thing in here?" in a single O(1) jump instead of an O(n) scan, deleting whole inner loops on sight and collapsing O(n²) to O(n). What can you buy by trading space for time? → When can grabbing the best-looking option right now possibly be the globally optimal move? →

06Hashing — buying O(1) with space

Almost every slow program is slow for one reason: somewhere inside a loop, it is searching — asking "is this thing in here?" and walking the whole collection to find out. This chapter hands you the single most powerful move in practical algorithms: turn that search into a jump. By the end you will look at any nested loop whose inner half is a lookup and delete the inner loop on sight — collapsing O(n²) into O(n) — using nothing but a set or a dict. Volume 1 chapter 7 showed you how a hash table works inside; here you learn what to do with it.

The question that costs O(n) — and the trick that makes it free

Start with the most ordinary question a program ever asks: "is X in this collection?" With a list, Python has no choice but to look. It starts at index 0 and compares, element by element, until it finds a match or falls off the end. If the thing is absent, it touches every element. That is a linear scan, and its cost grows in lockstep with the size of the list — one comparison per item, n items, O(n). We counted it, no hand-waving:

def scan_ops(haystack, needle):
    ops = 0
    for x in haystack:          # look at one element…
        ops += 1
        if x == needle:         # …compare it…
            return ops          # …stop the instant we match
    return ops                  # a MISS touched everything

for n in (10, 100, 1000, 10000):
    print(n, scan_ops(list(range(n)), -1))   # -1 is absent → worst case
# 10 10 · 100 100 · 1000 1000 · 10000 10000

Line by line: the loop visits elements one at a time; each visit is one ops += 1; a match returns early, but a value that isn't there forces the loop to the very end. The output is the whole story — the comparison count is exactly n. Double the list, double the work. A million-item list means a million comparisons for one "is it here?".

Now the trick. A set (and a dict, its key-value sibling) does not store your values in a row to be walked. It computes where the value belongs from the value itself: feed the value to a hash function, get back a number, use that number to jump straight to one slot. So membership is hash-the-query, jump, look — one hash, one jump, one compare, a cost that does not grow with n at all. That is O(1), "constant time." We timed the exact same "is this missing value here?" question against both:

import timeit
for n in (1_000, 10_000, 100_000, 1_000_000):
    lst, st = list(range(n)), set(range(n))
    t_list = timeit.timeit(lambda: -1 in lst, number=1000) / 1000
    t_set  = timeit.timeit(lambda: -1 in st,  number=1000) / 1000
    print(n, round(t_list*1e9), "ns   vs", round(t_set*1e9), "ns")
# 1000       6006 ns  vs 65 ns
# 10000     61067 ns  vs 37 ns
# 100000   600563 ns  vs 38 ns
# 1000000 6392406 ns  vs 39 ns   (6.4 MILLISECONDS vs 39 nanoseconds)

Read the two columns. The list column marches: 6 µs, 61 µs, 600 µs, 6.4 ms — a straight multiple of n, exactly as the op-count predicted. The set column does not move: ~38 nanoseconds whether it holds a thousand items or a million. At a million items the set answers the question roughly 160,000 times faster. (Timings are from this machine and will vary; the shape — one line climbing, one line flat — is universal.)

One question, made free. But the real prize isn't one lookup — it's what happens when a lookup was hiding inside a loop →

The set: membership and dedup in one pass

A set is a bag of unique, hashable values with no order and no duplicates — a dict that kept only the keys. Two everyday jobs fall out of it for free. First, membership: x in some_set is the O(1) jump you just met. Second, deduplication — collapsing a collection to its distinct values — because a set physically cannot hold the same value twice. Adding a value that's already there is a no-op:

plays = ["Levels", "Titanium", "Levels", "Wake Me Up", "Titanium", "Levels"]
unique = set(plays)
print(unique)         # {'Wake Me Up', 'Levels', 'Titanium'}  (order not preserved)
print(len(unique))    # 3  — six plays, three distinct songs

That set(plays) is a single pass — it hashes each of the six songs and drops it into its slot; repeats land on a slot that's already taken and vanish. One line, O(n), done. Compare the beginner's instinct — a nested loop that asks "have I seen this before?" by scanning a growing result list — which is O(n²) for the exact same answer. The set replaces that inner scan with a hash.

The tally: counting with a dict (and Counter)

Keep the keys, but give each one a value that counts. That is a tally: a dict from thing to how-many. For each item you jump to its key and bump the number by one — every step O(1), the whole tally O(n). The idiom uses .get(key, 0), which reads "the current count, or 0 if we've never seen this key":

tally = {}
for s in plays:
    tally[s] = tally.get(s, 0) + 1     # jump to s, read count, add 1, store
print(tally)     # {'Levels': 3, 'Titanium': 2, 'Wake Me Up': 1}

Three lines of mechanism: tally.get(s, 0) fetches the running count in O(1); we add one; tally[s] = … writes it back in O(1). No list, no scan, no re-counting — each play is touched exactly once. Python ships this pattern pre-built as collections.Counter, which does the same thing and adds the questions you actually ask of a tally:

from collections import Counter
print(Counter(plays).most_common(1))          # [('Levels', 3)]  — the top song
print(Counter("mississippi").most_common(2))  # [('i', 4), ('s', 4)]

That second line is a whole class of interview questions ("most frequent character", "top-k words", "find the anagram groups") reduced to one line — because counting is just hashing with a running total.

Membership, dedup, counting — all one pass because the lookup is free. Now the headline act: a lookup that was trapped inside a second loop, and how a dict sets it free →

The "seen" dict: how a hash deletes an inner loop

Here is the pattern that separates the two programmers from the volume's opening. Take two-sum: given a list of numbers and a target, find two of them that add to the target. The obvious solution tries every pair — for each number, loop over all the others looking for its partner. That inner loop is a search, and it runs for every element, so the cost is every-pair: n(n−1)/2, which is O(n²). We counted the pair-checks exactly:

def two_sum_naive(nums, target):          # O(n^2): every pair
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):   # the inner loop IS a search
            if nums[i] + nums[j] == target:
                return (i, j)

def two_sum_hash(nums, target):           # O(n): one pass, a dict remembers
    seen = {}                             # value → index we saw it at
    for i, x in enumerate(nums):
        need = target - x                 # the exact partner x is looking for
        if need in seen:                  # O(1) — ask the dict, don't scan
            return (seen[need], i)
        seen[x] = i                       # write x down; value → index seen

The insight is small and total. In the naive version, when we hold x we don't know where its partner is, so we search for it. But we know exactly what the partner must be: target - x. So instead of searching, we keep a "seen" dict of every number we've passed, and simply ask it "have you got target - x?" — an O(1) jump. The inner loop doesn't get faster. It disappears. We ran both and counted operations at the worst case (the answer is the last pair):

# n     naive ops     hash ops
# 10          45          10
# 100       4,950         100
# 1000    499,500        1000     ← n(n-1)/2 vs n

At n=1000 the nested loop does 499,500 pair-checks; the dict version does 1,000 lookups. That is not a tweak — it is 500× at a thousand items and 500,000× at a million. Two-sum is stepped line by line in trace T31; the point here is the move, not this one problem.

Remembering what you've seen kills the search. Remembering what you've already computed kills something bigger — repeated work →

The cache: answer each question once

The "seen" dict remembers values you've passed. A cache remembers answers you've computed, so you never compute the same one twice. This is memoization, and it is the same dict trick pointed at a function. The classic victim is naive recursive Fibonacci, which re-solves the same subproblems an exponential number of times. A dict cache turns the tree of repeated calls into a straight line:

cache = {}
def fib(n):
    if n < 2:
        return n
    if n not in cache:                    # already answered? jump to it
        cache[n] = fib(n-1) + fib(n-2)    # first time only: compute, store
    return cache[n]

Line by line: base cases return immediately; otherwise we ask the cache in O(1) whether we've solved this n before; if not, we compute it once and write it down; every later request for the same n is a free jump. The effect is violent. We instrumented both versions with a call counter:

# fib(30):
#   naive recursion : 2,692,537 calls
#   with the cache  :        59 calls

Two and a half million calls become 59. The naive tree recomputes fib(28) tens of thousands of times; the cache computes it once and answers the rest from memory. (The recursion tree exploding then collapsing is a live widget in the Algorithms Lab, and stepped in the traces.)

The bill: space, hashable keys, and the worst case

O(1) is bought, not free. Three costs come with it, and an engineer names them out loud.

Cost one — space. A set or dict holds your data plus a table of slots that is deliberately kept larger than the data (so collisions stay rare — Volume 1 chapter 7). Trading memory for time is the whole deal; on a huge dataset that memory can be the thing you don't have.

Cost two — the keys must be hashable. To hash a key its value must be fixed, so its hash never changes underneath the table. That means immutable keys only. Lists are mutable, so they're barred — loudly:

{ ["Levels", 200]: 1 }         # TypeError: unhashable type: 'list'
{ ("Levels", 200): 1 }         # fine — a tuple is immutable, so hashable
print([].__hash__)             # None   — lists opt out of hashing entirely

A list's __hash__ is literally None: it refuses to be a key. Tuples of immutable things are the standard fix — that's why grid coordinates, dates, and (name, version) pairs are so often tuples.

Cost three — O(1) is the average, not a guarantee. The jump is fast only when values scatter across slots. If many keys land in the same slot — a collision — the table has to walk that pile-up, and in the pathological case where everything collides, the lookup degrades to the very linear scan we were escaping. We forced it, with keys whose hash is a constant so they all target one slot:

class AllSame:                       # a deliberately terrible key
    def __init__(self, v): self.v = v
    def __hash__(self): return 42    # EVERY instance → the same slot
    def __eq__(self, o): return self.v == o.v

# building a set of these, timed on the test machine:
#   n=1000   0.030 s      n=2000   0.109 s      n=4000   0.442 s
#   → doubling n roughly QUADRUPLES the time: O(n^2) build, O(n) per op

When every key collides, doubling the data quadruples the work — the signature of O(n²). The O(1) promise didn't just weaken; it collapsed all the way back to a scan. In normal use this never happens, because a good hash function scatters keys evenly. But "normal use" assumes nobody is choosing the keys on purpose.

That attack has a name: hash flooding. Around 2011, researchers showed that many web platforms — Python, PHP, Java, Ruby, ASP.NET and more — built dicts from untrusted input (POST fields, JSON keys, HTTP headers) with a fixed, published hash function. An attacker could craft thousands of keys that all collide, turning one small request into an O(n²) grind that pinned a server's CPU. The fix Python shipped is quietly brilliant: randomize the hash. Each process seeds its string hash with a secret chosen at startup, so an attacker can't predict which keys collide. You can watch the seed change between runs:

# two separate Python processes, same line:
hash("Levels")   #  4417089987191320694   (first process)
hash("Levels")   #   -41086165888829000   (second process — different!)
hash(200)        #  200   (integers still hash to themselves, both runs)

Same string, different hash every process — that unpredictability is the defense. (Integers hash to themselves, which is why the crafted-collision demo above needed a broken __hash__: CPython's probing scatters even adversarial integer keys.) This is why you must never rely on a set or dict's iteration order being stable across runs, and why security-sensitive code exists to make hashing unguessable.

Hashing bought O(1) by scattering keys to random slots — deliberately destroying order for speed. The next chapter asks the opposite question: the next chapter buys that same speed for free — no extra memory at all — with two pointers and a sliding window: array sweeps that compute the change between overlapping states instead of restarting the work each time → →

07Two pointers & the sliding window

Chapter 6 bought speed with a hash table — extra memory in exchange for O(1) lookups. This chapter buys the same speed with nothing extra at all. You'll learn two array patterns that collapse a nested double loop into a single sweep: two pointers that march from both ends toward the middle, and a sliding window that reuses the work it already did instead of starting over. After this you'll be able to look at an O(n²) loop and see, instantly, whether it's secretly O(n) in disguise — and how to set it free.

Two fingers, marching inward

From Volume 1 you know an array is a row of contiguous slots, and that a[i] is a single multiply-and-jump — O(1) random access. The usual way to walk it is one index sliding left to right. But some problems have a hidden symmetry: the answer depends on the two ends at once. For those, put one finger on the first slot and one on the last, and step them toward each other until they meet.

Reversing a list is the cleanest case. Swap the two ends, then step both inward. When the fingers meet in the middle, you're done — you've touched each slot exactly once and never allocated a second array.

def reverse(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:                    # stop the instant they meet
        a[lo], a[hi] = a[hi], a[lo]   # swap the two ends in one statement
        lo += 1; hi -= 1              # step both pointers inward
    return a

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:            # a single mismatch settles it — bail early
            return False
        lo += 1; hi -= 1
    return True

print("".join(reverse(list("REWARD"))))   # DRAWER   (3 swaps for 6 letters)
print(is_palindrome("racecar"))           # True
print(is_palindrome("python"))            # False

Read reverse line by line. lo, hi start at the two ends. The while lo < hi guard is the whole trick — the loop runs only while the fingers haven't crossed. Each pass swaps the pair they point at and pulls both inward by one. For 6 letters that's 3 swaps (I ran it: REWARD → DRAWER); for n items it's exactly n // 2 swaps. Count the operations: one loop, running n/2 times, constant work inside — that's O(n) time. And crucially, O(1) extra space: no copy, no second array. is_palindrome is the same skeleton with a comparison instead of a swap, and it can bail early the moment two ends disagree.

Both-ends only helps when you act on both ends. But watch what happens when we point those two fingers at a sorted array and go hunting for a pair. →

When it's sorted, every look kills half the mistakes

Here's the classic: find two numbers in an array that add up to a target. The brute force is two nested loops — try every pair — which is n(n-1)/2 comparisons, O(n²). In chapter 6 we crushed it to O(n) with a hash "seen" set. But that costs O(n) extra space and works on any order. If the array is already sorted, two pointers do it in O(n) time and O(1) space — no hash at all.

Put lo at the smallest value, hi at the largest, and look at their sum. Now the magic, and it's worth savouring: because the array is sorted, that one comparison tells you exactly which pointer to move.

• If a[lo] + a[hi] is too small, no pair using a[lo] can ever reach the target — a[hi] is already the biggest partner available, and it wasn't enough. So a[lo] is hopeless: drop it, lo += 1.
• If the sum is too big, by the same logic a[hi] is hopeless with every remaining partner: drop it, hi -= 1.
• If it's equal, you found the pair.

Every single step permanently eliminates one number from all its remaining pairings — a whole row (or column) of that n² grid of pairs, gone. Since there are only n numbers to eliminate, the pointers meet in at most n − 1 steps.

def two_sum_sorted(a, target):        # a is sorted ascending
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi             # found it
        elif s < target:
            lo += 1                    # too small -> raise the low end
        else:
            hi -= 1                    # too big  -> lower the high end
    return None

a = [2, 7, 11, 15, 20, 24, 40]
print(two_sum_sorted(a, 26))          # (0, 5)  ->  2 + 24 = 26,  found in 2 steps

I instrumented both versions. On that little array the two-pointer walk found 2 + 24 = 26 in 2 steps. On a sorted array of 100,000 numbers it found a middle pair in 11,232 steps — comfortably under the n − 1 = 99,999 ceiling — while the brute force would have needed up to n(n−1)/2 ≈ 5,000,000,000 comparisons. Five billion versus eleven thousand, from the same data, just by letting sortedness do the eliminating.

The same "move the pointer that can't possibly help" idea powers container with most water: given wall heights, pick two walls holding the most water. Start wide, and always move the shorter wall inward — moving the taller one can only ever shrink the width without lifting the limiting height. I ran it on [1,8,6,2,5,4,8,3,7] → max area 49, in a single O(n) pass.

So far the pointers move toward each other. Now aim them the same way — one leading, one trailing — and the gap between them becomes a window you drag across the data. →

The sliding window: never recompute the overlap

New problem: in an array of numbers, find the largest sum of any k consecutive elements. The obvious approach: for each starting position, add up its k elements and keep the best. There are n − k + 1 windows and each costs k − 1 additions, so the total is (n − k + 1)(k − 1) — roughly n·k, which is O(n²) when k grows with n. I ran it for n = 1000, k = 100: 89,199 additions.

Now stare at two neighbouring windows. They overlap in k − 1 elements — almost everything. The brute force re-adds that shared middle every single time. That re-adding is the wasted work. Kill it: when the window slides one step right, the new sum is just the old sum, minus the element that fell off the left, plus the element that entered on the right. One subtraction, one addition — exactly 2 operations per step, no matter how big k is.

def max_window(a, k):
    s = sum(a[:k])              # first window: k-1 additions, paid once
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]    # +entering, -leaving : exactly 2 ops, any k
        if s > best:
            best = s
    return best

Line by line: sum(a[:k]) pays for the first window one time. Then r walks the entering index across the rest of the array. The single line s += a[r] - a[r-k] is the entire idea — a[r] joins, a[r-k] (exactly k slots back, the one falling off the left) leaves, and s is patched in O(1). No inner loop. Total work: (k − 1) for the first window plus 2 per slide — about 2n, which is O(n). I ran it against the brute force: same answer, but 1,899 additions instead of 89,199 — 47× fewer. On a bigger case (n = 200,000, k = 1000) the wall-clock was roughly 0.66 s → 0.014 s, about 46× faster on this machine (timings vary by hardware, but the shape doesn't).

Fixed-size windows are the easy half. The real power shows up when the window has to breathe — growing and shrinking on its own to keep some rule true. →

A window that breathes — grow right, shrink left

Problem: find the length of the longest substring with no repeated character. The window here isn't a fixed size — it's defined by an invariant: "the characters inside are all distinct." Keep two pointers, left and right. Push right forward to grow the window. The moment the new character is already inside, the invariant breaks — so pull left forward until it holds again. At every step, the window is the longest valid one ending at right; track the best length you ever see.

def longest_unique(s):
    last = {}                        # char -> most recent index it appeared
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1      # jump left PAST the earlier copy, in one move
        last[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))    # 3   ("abc")
print(longest_unique("playlist"))    # 6   ("aylist")

Walk it: last remembers where each character was seen (a hash — chapter 6 never really leaves you). For each new ch at index right, if we've seen it and its last position is inside the current window (>= left), we jump left to just past that old copy — restoring "all distinct" in a single move rather than stepping one at a time. Then we record ch's new position and update best. I ran it: "abcabcbb" → 3, and our running example "playlist" → 6 (the window "aylist", after the repeated l forces left forward).

Longest-valid grows greedily and shrinks only when forced. Flip the goal — find the smallest window that satisfies a condition — and the window learns a second move: squeeze. →

The minimum window — cover, then squeeze

The hardest classic in the family: given a text and a set of characters you need, find the smallest slice of the text that contains all of them. Think "shortest stretch of a log that mentions all three error codes." The window now works in two phases it alternates between: expand right until the window covers everything needed, then squeeze left as far as it can while staying covered — recording the smallest covered window each time — until it's no longer covered, and expand again.

The invariant tracker is a single counter, missing: how many needed characters are still uncovered. It updates in O(1) as characters enter and leave, so we always know the moment coverage flips — no rescanning the window to check.

from collections import Counter

def min_window(text, need):
    want = Counter(need)               # how many of each char we still want
    missing = len(need)                # total chars still uncovered
    left = 0
    best = ""
    for right, ch in enumerate(text):
        if want[ch] > 0:               # this char was actually needed
            missing -= 1
        want[ch] -= 1                  # may go negative: a surplus copy
        while missing == 0:            # covered! squeeze from the left
            if best == "" or right - left + 1 < len(best):
                best = text[left:right + 1]
            want[text[left]] += 1
            if want[text[left]] > 0:   # we just dropped a NEEDED char
                missing += 1           # uncovered again -> stop squeezing
            left += 1
    return best

print(min_window("ADOBECODEBANC", "ABC"))   # 'BANC'

The heart is the two counters. want[ch] tracks how many of each character the window still needs; it goes negative for surplus copies, which is what lets the squeeze phase know a character is expendable. missing hits 0 exactly when the window first covers the target — that's the trigger for the inner while, which shrinks from the left, each time checking if this is the smallest covered window yet, and stops the instant it drops a genuinely needed character (want[...] > 0 after adding it back). I ran it on the textbook input "ADOBECODEBANC" needing "ABC" → 'BANC', the shortest slice holding an A, a B, and a C. Same total-travel argument as before: both pointers only move forward, so it's O(text length), not O(n²).

The one move: reuse the overlap

There is, and it's the whole point of the chapter. A brute-force nested loop restarts its inner work from scratch at every outer step — re-summing an overlap, re-scanning for a partner, re-checking a window it just checked. But consecutive states of a scan overlap almost completely. The move that separates a coder from an engineer is to compute the change between states, not each state from zero. Two pointers and the sliding window are just the array-shaped incarnation of that one reflex: don't restart — update.

Where this reflex earns its keep in the wild goes far past interview arrays. Finance: a rolling volatility or a moving-average crossover is a sliding window over a price stream — recomputing the whole trailing average on every tick would be O(n·window); the delta update is O(1). Networking: TCP's window is why the internet doesn't melt under its own bookkeeping. Video codecs encode each frame as the difference from the last, not the whole picture again — the same "store the change" instinct at 30 frames a second. Rate limiters guarding every serious API are sliding windows of timestamps. Even your eyes, reading this line, drag a small focus window across the text rather than re-photographing the page each word.

The everyday transfer is real too. To answer "what changed in this document?" you don't re-read it top to bottom — you track the delta. When a list is sorted, you rarely need to inspect everything; you can walk from the ends and let the ordering eliminate whole regions, the way binary search bisects a bug. That is two-pointer thinking off the screen: let structure do the discarding, and never redo work you can update.

Every technique so far has been careful — reuse the overlap, restore the invariant, discard the impossible. Chapter 8 gets reckless on purpose: grab the best-looking option in front of you right now and never look back. It sounds like a way to be wrong — so when does that greedy gamble actually hand you the optimal answer, and when does it quietly betray you? →

08Greedy — when the local choice wins globally

A greedy algorithm makes the choice that looks best right now and never takes it back. That sounds reckless — and sometimes it is — but for a startling family of problems it lands the globally best answer with almost no work. This chapter teaches you the two things courses skip: exactly why greedy sometimes nails the optimum (the exchange argument), and exactly why it sometimes fails badly (a two-coin counterexample you'll run yourself). After it you'll be able to look at a new problem and say — before writing a line — whether the fast, simple, never-look-back move is safe, or a trap.

The greedy move: commit now, never look back

Every optimization problem hides a tree of choices. To make change for 6 units you could hand over a 4 then a 1 then a 1; or a 3 then a 3; or six 1s — each sequence of picks is a path down a branching tree, and the leaves are the finished answers. Brute force (chapter 4) walks the whole tree and compares every leaf. That is correct but explosive: a tree with a two-way choice at each of n steps has 2ⁿ leaves.

Greedy refuses to branch. At every node it applies one rule — "take the biggest coin that still fits", "take the meeting that finishes soonest" — commits to it, and descends. One path, root to leaf. No backtracking, no comparing alternatives. If the tree is n deep, greedy does O(n) work (plus, usually, an O(n log n) sort to decide the order it considers things in) where brute force does O(2ⁿ). The entire gamble is this: can a sequence of locally-best moves add up to the globally-best answer? When it can, you get an exponential speedup for free.

So what decides whether "best now" equals "best overall"? Let's find a problem where it's obviously true, and one where it's disastrously false. Start with the disaster. →

When greedy lies: the coin that costs you

Making change is the folk-tale example of greedy: to pay 87 cents, a cashier grabs a quarter, another quarter, another quarter, a dime, two pennies — biggest coin that fits, every time. For the coins in your pocket that habit is not just fast, it's optimal — it always uses the fewest coins. So people conclude greedy "usually works". Watch it break with a tiny change to the coin set.

def greedy(coins, target):
    n = 0
    for c in sorted(coins, reverse=True):   # biggest coin first
        while target >= c:                  # grab it while it fits
            target -= c
            n += 1
    return n

def optimal(coins, target):                 # dynamic programming — chapter 9
    best = [0] + [float("inf")] * target
    for amt in range(1, target + 1):        # smallest sub-amount up
        for c in coins:
            if c <= amt:
                best[amt] = min(best[amt], best[amt - c] + 1)
    return best[target]

print(greedy([1, 3, 4], 6))   # 3   ->  4 + 1 + 1
print(optimal([1, 3, 4], 6))  # 2   ->  3 + 3

Line by line: greedy sorts the coins large-to-small, then for each denomination subtracts it as many times as it fits, counting coins. optimal is the honest answer — it builds up best[amt] = the fewest coins for every amount from 1 to the target, each one reusing the smaller answers already computed (that's the dynamic programming of chapter 9; here it's just the referee). The last two lines are the verdict, and I ran them: greedy prints 3, optimal prints 2.

Greedy grabbed the 4 because it was biggest, then had to patch the leftover 2 with two 1s: 4 + 1 + 1, three coins. The right answer ignores the shiny 4 entirely: 3 + 3, two coins. The greedy criterion — "biggest first" — walked confidently into a worse leaf and, having no backtracking, never noticed. Across the first 100 targets with the set [1, 3, 4], greedy is beaten on 24 of them (6, 10, 14, 18, 22, …). It isn't occasionally unlucky; it is systematically wrong for this coin system.

If greedy is a claim, we need to test the claim. When it's true, there's a beautiful reason — and it comes with its own famous winning problem. →

The exchange argument: proving greedy right

Here is the problem greedy was born for. You have one lecture hall and a pile of talks, each with a start and finish time; overlapping talks can't share the room. Which talks do you accept to fit the most into the day? The winning rule is almost insultingly simple: always take the talk that finishes earliest among those that still fit. Not the shortest, not the earliest-starting — the earliest-finishing.

def schedule(acts):                       # acts: (name, start, finish)
    chosen, last_finish = [], -1
    for name, s, f in sorted(acts, key=lambda a: a[2]):   # by finish time
        if s >= last_finish:              # doesn't overlap what we took
            chosen.append(name); last_finish = f
    return chosen

acts = [("A",1,4),("B",3,5),("C",0,6),("D",5,7),
        ("E",3,9),("F",5,9),("G",6,10),("H",8,11)]
print(schedule(acts))     # ['A', 'D', 'H'] — 3 talks

The loop sorts by finish time, then walks once: keep a talk only if it starts at or after the last kept talk ended. I ran it against a brute-force check of every one of the 2⁸ possible talk subsets — the biggest compatible set really is 3, and greedy finds it. Why does finishing-earliest win? Because it leaves the room free as early as possible, which can never hurt: the more time left, the more room for what's next.

That intuition becomes a proof by the exchange argument — the master key for every greedy correctness claim. Take any optimal schedule. Look at its first talk versus greedy's first talk. Greedy's finishes no later (that's how greedy chose it). So swap the optimal's first talk for greedy's: the new first talk frees the room at least as early, nothing else overlaps, and the schedule is still valid and still the same size — still optimal. Repeat down the line, and you've morphed some optimal solution into greedy's, step by step, without ever losing a talk. So greedy's answer is optimal too. No choice greedy makes can be "traded up" to a better one — because the best solution can always be traded down to greedy's.

Why earliest-finishing and not, say, shortest? Because a different rule fails the exchange test — and you can catch it with a three-talk counterexample. Take X(1–5), Y(4–7), Z(6–10). "Shortest first" grabs Y and blocks both X and Z, ending with 1 talk. Earliest-finish grabs X then Z — 2 talks. I ran both; the numbers are exactly that. The criterion isn't decoration; it's the whole proof.

One earliest-finish rule, one exchange proof, an exponential speedup. Now meet the greedy algorithm running silently inside almost every file on your disk. →

Huffman: the greedy algorithm in every file you own

Text is stored as bits. The lazy scheme gives every character the same width — 8 bits in ASCII — whether it's a hyper-common e or a rare q. That's wasteful: frequent symbols should get short codes and rare ones can afford long codes, like Morse code giving e a single dot. In 1952 a student named David Huffman found the provably shortest such code, and the algorithm is pure greed: repeatedly merge the two rarest symbols into one combined node, until a single tree remains.

import heapq

def huffman(freq):
    forest = [[w, i, {s}] for i, (s, w) in enumerate(freq.items())]
    heapq.heapify(forest)                    # a min-heap by weight
    code, nxt = {s: "" for s in freq}, len(freq)
    while len(forest) > 1:
        w1, _, s1 = heapq.heappop(forest)    # the rarest bundle
        w2, _, s2 = heapq.heappop(forest)    # the next rarest
        for s in s1: code[s] = "0" + code[s] # prepend a bit to each side
        for s in s2: code[s] = "1" + code[s]
        heapq.heappush(forest, [w1+w2, nxt, s1|s2]); nxt += 1
    return code

freq = {"a":45, "b":13, "c":12, "d":16, "e":9, "f":5}
code = huffman(freq)
bits = sum(freq[s] * len(code[s]) for s in freq)
print(bits, "vs", 3 * sum(freq.values()))   # 224 vs 300

The forest starts as one tiny tree per symbol, kept in a min-heap (chapter-1 structure) so "the two rarest" is always two heappops. Each round fuses them: every symbol on the left branch gets a 0 prepended to its code, every symbol on the right a 1, and the merged node (its weight the sum) goes back in the heap. After n−1 merges one tree is left, and each symbol's code is the path of 0s and 1s from the root. I ran it: the classic frequencies compress to 224 bits versus 300 for a fixed 3-bit code — a (the most common) got the 1-bit code 0, while rare f got 1100. That's a 25% saving, and it is provably the smallest any code can achieve for these frequencies.

Because every symbol is a leaf, no code can be the start of another one — the instant the bits trace a path down to a leaf, that's the letter, and decoding jumps back to the root for the next. This prefix-free property is the quiet genius of building codes from a tree: the stream is unambiguous with no separators at all. That's not a lucky side effect of greed — it's guaranteed, because greedy only ever puts symbols at leaves.

The knob below is why compression works at all. Skew the frequencies and watch the savings appear; flatten them and watch the savings vanish. It runs the real Huffman merge live.

Greedy commits to one choice and proves it never needed the others. Its rival keeps all the choices alive. Time to put them face to face. →

Greedy vs dynamic programming: commit vs consider

The coin change split the world in two. Greedy took the biggest coin and moved on. The optimal function did something different: it computed the best answer for every smaller amount and combined them — it never committed early, it kept every sub-answer and reused them. That's dynamic programming (chapter 9), and the contrast is the cleanest way to understand both.

Two techniques, one decision. So how do you know, on a brand-new problem, which one you're holding — before you've bet the system on it? →

How to know before you trust it

You'll rarely be told "this is a greedy problem". You'll be handed a goal — schedule the most jobs, wire the network for the least cable, route the packet the cheapest way — and you have to decide whether the greedy shortcut is a proof or a trap. Here is the drill, and it's the same every time.

Name the greedy rule ("take the earliest-finishing", "merge the two rarest"). Then run two attacks in parallel. Prove it: can you show the greedy choice is always swappable into some optimal solution — the exchange argument? If yes, you're done — greedy is optimal and fast. Break it: at the same time, throw small inputs at it and compare against a brute-force referee, exactly as we did with the coins. A single counterexample kills greedy forever; you don't get to say "but it works most of the time". If it breaks, you already know the escape hatch: dynamic programming.

This chapter's real gift is a way of thinking, and it's bigger than algorithms. You use greedy reasoning every day: paying with the biggest bills, running errands nearest-first, packing the fullest boxes. It's a superb heuristic — a fast, good-enough rule of thumb. The 1% move is to hold two thoughts at once: reach for the simple local rule first, and in the same breath ask what it's ignoring. Greedy fails exactly when a locally-worse choice now buys a better position later — the 3 you skipped, the talk you passed up, the move that sets up the next three. Naming that failure mode is a life skill: it's why you sometimes take the smaller reward now to keep the bigger one open, and why "obviously best right now" always deserves one hard look before you commit.

But the coin change that greedy botched still needs its right answer — and so do knapsacks, edit distance, and the longest path through a lattice of choices. The fix is to stop re-solving what you have already solved. Chapter 9 turns "remember your subproblems" into the most powerful technique in this whole volume: dynamic programming. →

09Dynamic programming — remember to win

This is the crown jewel of the volume. Dynamic programming — DP — is the single move that turns problems the universe couldn't finish before it ends into problems your laptop finishes in a blink. The whole trick is embarrassingly human: never solve the same sub-problem twice. By the end you will be able to look at a fresh problem, decide in seconds whether DP fits, name its state, write its recurrence, and fill a table that hands you the answer — the exact skill that separates the engineer the interviewer remembers from the one they forget.

The two signals that scream "dynamic programming"

Start where you already stand. In the traces you stepped naive Fibonacci (T29) and its memoised twin (T30). Naive Fibonacci is three honest lines: fib(n) returns n when n < 2, otherwise fib(n-1) + fib(n-2). It is correct. It is also a catastrophe — and watching why is the whole chapter in miniature.

Count the calls, don't guess them. Let C(n) be the number of times fib is invoked to compute fib(n). Every call either stops immediately (n < 2) or spawns two more, so C(n) = 1 + C(n-1) + C(n-2) — the count itself grows like Fibonacci. The tree of calls nearly doubles at every level, and that is the definition of exponential. Here is the real toll, measured, not imagined:

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

for n in [30, 35, 40]:
    calls = 0; v = fib(n)
    print(n, v, calls)
# 30 832040    2692537
# 35 9227465   29860703
# 40 102334155 331160281

Read those counts. Computing fib(35) — one small number — cost 29,860,703 function calls. Push to fib(40) and it is 331 million. Extrapolate honestly (the count formula is C(n) = 2·fib(n+1) − 1) and fib(100) would take about 1.15 × 10²¹ calls — at the roughly 30 million-calls-per-second this machine managed, on the order of a million years (order-of-magnitude; timings are machine-dependent). For a problem a child can do on paper.

Where is all that work going? Nowhere new. The tree for fib(5) asks for fib(3) twice, fib(2) three times, fib(1) five times — the same tiny questions, re-asked, re-answered, from scratch, forever. That is the first signal, and it has a name.

Signal one — overlapping sub-problems: the recursion keeps bumping into the same smaller problem. (Contrast merge sort in ch5: it splits into fresh, non-overlapping halves — no repeats, so no DP needed.) Signal two — optimal substructure: the best answer to the whole is built from best answers to its parts. fib(n) is literally fib(n-1) + fib(n-2); the shortest route through a city is shortest-route-to-here plus one more step. Richard Bellman, who developed DP in the 1950s, called this the principle of optimality. When both signals fire, you are looking at a DP problem — and you are about to stop wasting a million years.

Two directions, one idea: memoise down, tabulate up

Keep a notebook. The first time you compute fib(k), store it; every later time, read it back instead of recomputing. That's memoisation — top-down DP: still recursive, but each distinct sub-problem is solved exactly once. Count the calls again and the collapse is total.

def fib_memo(n, memo):
    if n in memo:            # already solved? read it back — O(1)
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]           # write the answer down before returning

# fib_memo(35, {}) makes 69 calls, not 29,860,703.
# fib_memo(100, {}) makes 199 calls — the "million years" becomes microseconds.

Line by line: if n is in the notebook, hand it back — this is the line that kills the redundancy. Otherwise handle the two base cases, then compute the two smaller Fibonaccis once, store the sum in memo[n], and return it. Because each n from 0 to the target gets filled exactly once and then only ever read, the number of calls drops from exponential to 2n − 1 — 69 calls for fib(35), 199 for fib(100). Same three-line logic; one dictionary; an astronomically different bill. Measured on this machine, naive fib(35) took about 1.0 s and the memoised version about 18 microseconds — roughly a 50,000× gap (machine-dependent, but the shape of the gap is not). (You don't even have to write the notebook by hand: Python's @lru_cache from functools — Volume 1 ch11 — bolts this exact memoisation onto any function with one line.)

There is a second way to hold the same idea, and it is often the better one. Instead of recursing down and caching on the way back, walk up: fill a table from the smallest sub-problem to the biggest, in an order where every value you need is already sitting there. That's tabulation — bottom-up DP.

def fib_table(n):
    dp = [0, 1] + [0]*(n-1)          # dp[k] will hold fib(k)
    for k in range(2, n+1):
        dp[k] = dp[k-1] + dp[k-2]    # both already filled — just read them
    return dp[n]

No recursion, no call stack, no dictionary — one array, filled left to right, each cell reading its two neighbours. It's O(n) time and (with two rolling variables) O(1) space. Same recurrence as memoisation, run in the opposite direction.

So the fix is a notebook. But Fibonacci handed us the recurrence for free. The real skill — the thing that actually separates people — is inventing the recurrence for a problem nobody wrote down for you. There's a procedure for that. →

The recipe: name the state, write the recurrence

Everyone can memoise a function someone else wrote. The rare skill is turning a word problem into a table. It is not inspiration — it is a five-step procedure you can run on anything:

1. Define the state. Decide what a sub-problem is, and write down in one plain sentence what dp[…] means. This is 80% of the work. Get it right and the rest falls out.
2. Write the recurrence. Express dp[state] using strictly smaller states — the same "best of parts" the problem's optimal substructure promised.
3. Fix the base cases. The smallest states you can answer with no recurrence at all.
4. Choose the fill order. Any order where a cell's dependencies are computed before it.
5. Read off the answer. Name the cell that holds it.

Run it on coin change: given coin values and a target amount, what is the fewest coins that make the amount? State: dp[a] = the fewest coins that make amount a. Recurrence: to make a, the last coin is some c; whatever's left is a − c, which we've already solved — so dp[a] = 1 + min(dp[a − c]) over every coin c ≤ a. Base: dp[0] = 0 (zero coins make zero). Order: a from small to large. Answer: dp[amount].

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF]*amount          # dp[0]=0; the rest "unknown"
    for a in range(1, amount+1):
        for c in coins:              # try every coin as the LAST coin
            if c <= a:
                dp[a] = min(dp[a], dp[a-c] + 1)
    return dp

print(min_coins([1,3,4], 6))
# [0, 1, 2, 1, 1, 2, 2]  ->  dp[6] = 2   (that's 3+3)

Line by line: dp starts with dp[0]=0 and everything else infinite ("no way found yet"). The outer loop walks amounts upward; the inner loop tries each coin as the final coin and keeps the cheapest option. When it finishes, dp[6] = 2 — two coins, the pair of 3s. Notice what the table exposes: greedy (ch8) would grab the biggest coin first — 4 + 1 + 1 = three coins — and lose, because on the denominations [1,3,4] the locally-best move isn't globally best. DP doesn't guess a strategy; it quietly considers every last coin and remembers the winner.

Coin change had a one-dimensional state — a single number a. Some problems need the table to grow a second axis. That's where DP starts to feel like real power. →

0/1 knapsack — the value-under-a-budget grid

You have a weight budget and a set of items, each with a weight and a value; take each item once or not at all; maximise total value without blowing the budget. This is the shape of a thousand real decisions — which features fit in a sprint, which trades fit a risk limit, which files fit on the disk. Greedy by "best value-per-kilo" can fail here too. DP cannot.

The state needs two facts: which items you're allowed to consider, and how much budget is left. State: dp[i][w] = the best value using only the first i items within a budget of w. Recurrence: for item i you make one binary choice — skip it (dp[i-1][w]) or, if it fits, take it (dp[i-1][w − weight_i] + value_i) — and keep the larger. Base: zero items or zero budget → value 0. Answer: dp[n][W].

items = [("guitar",1,1500), ("laptop",3,2000),
         ("stereo",4,3000), ("necklace",2,2500)]   # (name, weight, value)
W = 4
wt  = [w for _,w,_ in items]; val = [v for _,_,v in items]; n = len(items)
dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        dp[i][w] = dp[i-1][w]                         # skip item i
        if wt[i-1] <= w:                              # if it fits, try taking it
            dp[i][w] = max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1])

print(dp[n][W])   # 4000  — guitar (1kg,1500) + necklace (2kg,2500)

Line by line: dp is an (n+1) × (W+1) grid of zeros — the base row and column. For each item and each budget, first assume we skip it (inherit the answer from the row above). Then, if the item fits, compare against taking it: its value plus the best we could do with the remaining budget w − weight using the earlier items. Keep the max. The final cell dp[4][4] is 4000 — and it's the light, valuable pair (guitar + necklace), not the single 3000 stereo that a value-greedy grab might chase. Two nested loops, O(n·W) cells, each O(1): the whole grid is one cheap sweep.

Coin change and knapsack both optimised a number. The most beautiful DP of all optimises something you touch every hour without noticing: the distance between two pieces of text. →

Edit distance — the algorithm inside diff, spell-check, and DNA

How different are two words? Define it precisely: the edit distance (Levenshtein distance) between strings a and b is the minimum number of single-character inserts, deletes, and substitutions to turn one into the other. "color" → "colour" is 1 (insert a u). "kitten" → "sitting" is 3. And the way we compute it is the same table-filling move — now on a grid.

State: dp[i][j] = the edit distance between the first i letters of a and the first j letters of b. Recurrence: look at the last letters. If a[i-1] == b[j-1], they cost nothing — the answer is dp[i-1][j-1]. If they differ, you must do one edit, and you take the cheapest of three moves: delete a's last letter (dp[i-1][j] + 1), insert b's last letter (dp[i][j-1] + 1), or substitute (dp[i-1][j-1] + 1). Base: turning a length-i word into the empty string costs i deletes, so dp[i][0] = i and dp[0][j] = j. Answer: the bottom-right cell.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i        # a[:i] -> ""  costs i deletes
    for j in range(n+1): dp[0][j] = j        # "" -> b[:j]  costs j inserts
    for i in range(1, m+1):
        for j in range(1, n+1):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1,        # delete
                           dp[i][j-1] + 1,        # insert
                           dp[i-1][j-1] + cost)   # match / substitute
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3
print(edit_distance("recieve", "receive"))  # 2   (the classic typo)
print(edit_distance("color",   "colour"))   # 1

Line by line: build the grid, seed the first row and column with the "delete/insert everything" base costs, then fill each interior cell from its three neighbours — up (delete), left (insert), and up-left (match or substitute, free if the letters agree). The bottom-right cell is the answer. Here is the actual table Python filled for kitten → sitting — trace the diagonal of small numbers and you can literally read the alignment:

Now build it yourself. Drag the slider and watch the grid fill in reading order — each interior cell lighting up its three source neighbours and showing the exact min(…) it evaluates. This is the "fill the grid" mental model made physical: nothing here is clever per cell; the whole answer emerges from local moves.

Notice the human move that unlocked all of this. Comparing two whole strings is hopeless — too many alignments. The insight was to stop comparing the wholes and compare all their prefixes: once you know the distance for every shorter pair, the full pair is one cheap step away. That reframing — "solve it for all smaller versions and the big version is trivial" — is the beating heart of DP, and it was independently discovered in linguistics, computer science, and molecular biology because it is simply how this class of problem wants to be solved.

Two more shapes: common subsequence & increasing subsequence

Once you can spot the state, new problems stop feeling new. Two you'll meet constantly:

Longest common subsequence (LCS) — the longest run of characters appearing in both strings in order (not necessarily adjacent). Its state is edit distance's cousin: dp[i][j] = LCS length of the first i of a and first j of b; if the last letters match, dp[i-1][j-1] + 1, else max(dp[i-1][j], dp[i][j-1]). This is the engine of git diff: the unchanged lines between two file versions are exactly their LCS, and everything else is an add or a delete.

Longest increasing subsequence (LIS) — the longest run of values that increases, picked from a list in order. State: dp[i] = the length of the longest increasing subsequence ending at index i. Recurrence: dp[i] = 1 + max(dp[j]) over every earlier j with seq[j] < seq[i]. Both were run in Python:

lcs("ABCBDAB", "BDCAB")            # length 4  -> "BCAB"
lis([10, 9, 2, 5, 3, 7, 101, 18]) # length 4  -> [2, 5, 7, 101]
# per-index dp for LIS: [1, 1, 1, 2, 2, 3, 4, 4]

Read the LIS dp array: at index 6 (value 101) the best increasing run ending there is length 4 — it chained through 2, 5, 7. The answer is the max over the whole array. That's O(n²) here (each cell scans all earlier cells); a sharper version uses binary search (ch12) to reach O(n log n) — a preview of how one technique feeds the next.

You've now filled five different tables with one procedure. Time to name the mental move you actually installed — and know exactly when it will and won't save you. →

When to reach for it — and the move you keep

Reach for DP when both signals fire: overlapping sub-problems (you keep re-solving the same smaller thing) and optimal substructure (the best whole is built from best parts). Miss either and DP is the wrong tool. No overlap? You have plain divide-and-conquer (ch5) — merge sort gains nothing from a memo because its halves never repeat. No optimal substructure? Neither greedy nor DP is guaranteed, and you may be forced to search everything (ch10).

It helps to place DP among its neighbours. Divide-and-conquer splits into independent pieces and never looks back. Greedy (ch8) commits to the best-looking move and never reconsiders — fast when it's provably right, wrong on [1,3,4] coins. DP is the careful middle: it considers every choice like brute force, but remembers each sub-answer so it pays for each only once. That's why the one-liner for DP is "brute force that doesn't repeat itself."

And here is the space bonus most people skip: once you have the recurrence, look at what each cell actually depends on. Fibonacci's dp[k] needs only the last two cells — so keep two variables and drop O(n) memory to O(1). Edit distance's row i depends only on row i-1 — so keep one row and drop O(m·n) space to O(min(m,n)). The recurrence tells you not just the answer but exactly how little you need to remember.

So the arc of this chapter is a single sentence: spot the overlap, define the state, write the recurrence, fill the table — and a problem that would outlast the universe finishes before your coffee cools. That is dynamic programming, and it is, more than any other single idea in this volume, the one interviewers use to separate the 1% from the rest.

DP works only when sub-problems overlap. But what about the problems where they don't — where every path is unique and the tree of choices is astronomically wide, yet most branches are hopeless the moment you start them? Next: recursion & backtracking — how to search a giant tree of choices, and how pruning a doomed branch turns "explores a billion dead ends" into "explores a thousand live ones." DP was backtracking that remembered; ch10 is backtracking that knows when to quit. →

10Recursion & backtracking — searching a tree of choices

Some problems have no clever formula. The only honest answer is: try the possibilities — arrange the songs, place the queens, fill the grid. Do it naively and you drown in an ocean of combinations. This chapter hands you the two tools that turn that ocean into a puddle: recursion to explore the possibilities one choice at a time, and backtracking to slam the door on billions of dead ends before you ever walk through them. After it you'll be able to look at "find a valid/optimal arrangement" and see a tree of choices — and know exactly where to prune it.

Recursion: shrink the problem until the answer is obvious

Recursion is one idea: solve a big problem by solving a smaller version of the same problem, and keep shrinking until the version is so tiny the answer needs no thought at all. That tiny, no-thought version is the base case — the floor you fall to. Every step above it is the recursive case — do a sliver of work, then hand the rest to a smaller copy of yourself.

Take the total length of a playlist. The total of [200, 247, 245] is "the first song, plus the total of everything after it." That second half is the same problem on a shorter list. Shrink it far enough and you hit the empty playlist, whose total is obviously 0. That is the whole recipe.

def total(songs):
    if not songs:                       # BASE CASE: empty list → answer is 0
        return 0
    return songs[0] + total(songs[1:])  # first + total of the REST (a smaller list)

print(total([200, 247, 245]))           # 692
print(total([]))                        # 0

Line 2–3 is the floor: an empty playlist sums to 0, no recursion needed. Line 4 is the shrink: peel off songs[0], then ask the very same function to total songs[1:] — a list one shorter. Ran on CPython 3.12.7, total([200, 247, 245]) returns 692 (200 + 247 + 245) and total([]) returns 0. Notice there is no loop anywhere. The repetition is the function calling itself.

Where does the machine keep its place across all those nested calls? On the call stack — Volume 1, chapter 9. Each call gets a frame: a scrap of memory holding that call's own songs, frozen mid-addition, waiting for its smaller copy to return a number. The frames stack up until the base case, then collapse back down, each one finishing its + with the value handed up from below. The call stack is recursion's bookkeeping — you don't manage the partial state, the stack does.

Summing a list only ever shrinks one way — chop the head, recurse on the tail, a straight line down. But what if at each step you face several options? Then the single line splits into a branching tree — and trees grow fast. →

Every choice sprouts a branch — the combinatorial explosion

Recursion becomes powerful — and dangerous — the moment each step offers more than one option. Then it stops drawing a line and starts drawing a tree of choices: the root is "nothing decided yet," each branch is one option, and each leaf at the bottom is one complete solution. To generate every possibility, you walk every branch.

Count the leaves and you feel the danger. Arrange 3 songs in order: the first slot has 3 candidates, then 2 remain for the second, then 1 — that's 3 × 2 × 1 = 6 = 3! orderings (a permutation is one ordering of all the items). Pick a subset instead — each song is independently in or out — and you get 2 × 2 × 2 = 2³ = 8 subsets. We didn't assert those numbers; we counted the choices at each level and multiplied. That multiplication is the whole story of why brute force dies.

Because it doesn't add — it multiplies. Ten songs: 10! = 3,628,800 orderings, still nothing. Twenty songs: 20! = 2,432,902,008,176,640,000 — 2.4 quintillion. At a billion arrangements per second that's about 77 years to merely list them (both figures computed in Python below). Add one more item and you multiply the wait again. This is the combinatorial explosion, and it is the reason the rest of the chapter exists.

If listing 20! possibilities takes 77 years, brute force is hopeless — yet solvers crack far harder-looking puzzles in milliseconds. Their secret isn't a faster computer. It's refusing to visit most of the tree. →

Backtracking: walk the tree, undo on the way back

Backtracking is how you actually traverse a choice tree without building it all in memory at once. You go depth-first: make one choice, dive deeper as if it were final, and when you've either found a solution or run out of options, step back and undo that choice so the next branch starts from a clean slate. Three beats, forever: choose → explore → un-choose. That un-choose is the "back" in backtracking — it restores the shared partial state so the sibling branch isn't polluted by the one you just abandoned.

Here it is generating every subset of the playlist. At each song you branch twice: skip it, or take it. Two options × n songs = 2ⁿ leaves, exactly as we counted.

def subsets(items):
    out, chosen = [], []
    def bt(i):
        if i == len(items):        # reached the bottom: record this subset
            out.append(chosen.copy())
            return
        bt(i + 1)                  # BRANCH 1: skip items[i]
        chosen.append(items[i])    # CHOOSE items[i]
        bt(i + 1)                  # BRANCH 2: explore with it taken
        chosen.pop()               # UN-CHOOSE — restore state for the caller
    bt(0)
    return out

print(subsets(["Levels", "Titanium", "Wake Me Up"]))

Line 4–6 is the base case: once i walks past the last song, chosen holds one complete subset, so we save a copy (not the live list — it's about to change). Line 8 explores the "skip this song" branch. Lines 9–11 are the choose/explore pair: append the song, recurse to decide the rest with it included. Line 12 is the crucial un-choose: chosen.pop() removes the song so that when control returns to the caller, chosen looks exactly as it did before this call meddled with it. Ran on 3.12.7, the call produces all 8 subsets — from [] through ['Levels', 'Titanium', 'Wake Me Up']. Swap the two-way branch for a "place each item that's still unused" loop and the identical pattern spits out all 6 permutations of [1, 2, 3]: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] (also a real run).

So far we still visit all 2ⁿ leaves — we've organised the search, not shortened it. The real magic is a single extra if: check a partial solution before descending, and cut whole subtrees you can prove are hopeless. →

Pruning: the whole game

Here is the idea that separates a toy from a solver. As you build a solution one choice at a time, keep asking: can this partial choice possibly complete into a valid answer? The instant the answer is "no," abandon the entire subtree beneath it — every arrangement that started with this bad prefix is dead, so you never generate a single one of them. That is pruning, and it is the difference between exploring 10⁹ dead ends and 10³ live ones.

The classic showcase is the N-queens puzzle: place N chess queens on an N×N board so none attacks another (no two share a row, column, or diagonal). Put one queen per row — that guarantees no row-clash for free — and at each row try each column. The pruning rule: the moment a queen conflicts with one already placed, skip that column entirely; don't recurse into the rows below it. A whole doomed subtree vanishes.

Count the savings on the standard 8×8 board — and watch three numbers fall off a cliff. Place 8 queens on any of 64 squares blindly: that's C(64,8) = 4,426,165,368 placements — 4.4 billion (computed in Python). Be a little smarter, one queen per row, all column combinations: 8⁸ = 16,777,216 leaves. Now add the pruning if, and backtracking touches just 2,057 partial placements to find all 92 solutions — over 8,000× fewer nodes than even the row-by-row brute force, and two million times fewer than the naïve count. Same puzzle. One conditional. The tree barely grows before pruning mows it down.

Turn the knob yourself. Below, slide N and compare the brute-force tree against what backtracking actually visits — the gap is the wasted work you never do.

Pruning tames N-queens because a bad prefix is provably hopeless. But some problems hide their answer so well that no pruning rule cracks the tree open. What then? →

When the tree won't shrink: NP-hard, and taming the beast

For some problems, nobody has found a pruning rule (or any trick) that reliably avoids the exponential — and there's deep evidence none exists. These are the NP-hard problems. The travelling salesman: visit N cities by the shortest possible loop. With 20 cities there are (20−1)!/2 = 60,822,550,204,416,000 distinct tours — 60 quadrillion, computed in Python. SAT (is there an assignment of true/false making a logic formula true?) has 2ⁿ assignments. There is no known algorithm that beats the exponential in the worst case for either. The tree is genuinely dense with plausible-looking branches.

And yet we solve big instances daily. Not by a magic fast algorithm — by taming the tree with three moves you can name:

• Branch and bound — carry a running "best answer so far," and before exploring a subtree, compute a bound on the best it could possibly yield. If even the optimistic bound can't beat what you already have, prune it. (Pruning, upgraded from "invalid" to "can't-win.")
• Heuristics / ordering — try the most promising branch first. The order you visit children in doesn't change the answer, but it changes how fast you find a good "best so far," which lets branch-and-bound prune harder. Chess engines order moves this way.
• Constraint propagation — after each choice, cheaply deduce forced consequences that shrink the remaining options (a sudoku solver fills every forced cell before it ever guesses).

This is why real SAT solvers chew through formulas with millions of variables, why sudoku apps solve instantly, and why chess AI before neural networks was backtracking the game tree with alpha-beta pruning — the same "this branch can't beat what I've found, cut it" logic. The exponential never went away; it got outmanoeuvred.

Branch and bound prunes by "can't win." But there's a fourth weapon, and it's the bridge to the crown jewel of the last chapter: what if the tree keeps re-solving the same subproblem? →

Backtracking + memory = dynamic programming (the mental move)

Walk a choice tree and you'll often notice the same subproblem showing up on many different branches. The naïve recursive Fibonacci is the purest example (stepped in traces T29/T30): fib(5) calls fib(3) down two separate paths, and each rebuilds the same subtree from scratch. The tree is exponential not because the answer is hard, but because you keep re-deriving what you already knew.

The fix is one line of thinking: remember the answers you've already computed. Cache each subproblem's result the first time; on every later encounter, read it instead of recomputing. That collapses the exponential tree into a linear walk. Backtracking that caches overlapping subproblems is dynamic programming — chapter 9's crown jewel is exactly this chapter's search plus a memo. The two conditions to look for: the subproblems overlap (worth caching), and the best full answer is built from best sub-answers (safe to build up).

That reframing is the transferable move — the 1% habit this chapter installs. Faced with any "find a valid or optimal arrangement," don't reach for a formula. Ask three questions in order: (1) Can I frame this as building a solution one choice at a time — a tree of choices? (2) Can I prune — is there a cheap test that proves a partial choice is hopeless, so I skip its subtree? (3) Do subtrees repeat — should I memoise? Choice-tree, then prune, then memo. That sequence turns "impossible, 2.4 quintillion cases" into "feasible, a few thousand."

You already run a crude version of this off-screen. Debugging: you form a hypothesis, follow it, and the moment the evidence contradicts it you abandon that whole line of theories instead of stubbornly exploring a dead branch — that's pruning. Planning a route through errands, ruling out a plan the instant it can't fit your lunch meeting — pruning. Backtracking isn't an exotic algorithm; it's the disciplined, countable version of how a careful mind already searches. Learn to name the tree and the prune, and you can attack problems that have no formula at all.

Backtracking searches when there's no formula. Next we return to a problem that does have fast algorithms — sorting — and meet a stunning result: a hard mathematical ceiling proving you can never sort by comparisons faster than n log n… and the clever trick that sneaks under it anyway. A beautiful impossibility, in chapter 11. →

11Sorting, properly — and a beautiful impossibility

You already own the five classic sorts: you stepped them line by line in the trace walkthroughs and raced them in the Algorithms Lab. This chapter is not about how they work — it is about the wall they all slam into, and the one trick that walks straight through it. By the end you will be able to prove, on the back of a napkin, that no sort built from comparisons can ever beat n log n — and then sort a million items in a single linear pass, faster than that limit, by refusing to compare at all.

The five sorts share one hidden move

Bubble, selection, insertion — the three that cost O(n²) when the list is big. Merge and quicksort — the two that cost O(n log n) and win at scale. Five different dances, and the Lab lets you watch each one shuffle the bars into place. But squint at any of them and you see the same atomic move repeated: pick two items, ask which is bigger, act on the answer. Everything else — the swaps, the splits, the merges — is bookkeeping around that one question.

That shared move is the key to the whole chapter. If the only thing your algorithm can learn about the data is the outcome of a < b questions, then the number of questions is the true cost, and there is a hard floor on how few you can get away with. Call any such algorithm a comparison sort. All five of yours are comparison sorts. So is almost every sort you have ever seen.

The speed limit — and why nobody can break it

Here is the most beautiful argument in this volume, and it is pure counting. Lay out every decision your sort could make as a tree. At the top, the first comparison it does. Two branches — yes and no — lead to the next comparison, which depends on the answer. Keep going. This is a decision tree: internal nodes are comparisons, each edge is an answer, and every path from the top down is one possible run of the algorithm on some input.

Where does a path end? At a leaf — the moment the sort stops asking and commits to an output order. Now the punch line. A list of n distinct items has n! possible starting arrangements (n choices for first, n−1 for second, and so on), and each one needs a different reshuffle to come out sorted. So the tree must have at least n! leaves — one distinct verdict per arrangement. Miss even one, and there is an input your sort gets wrong.

Now weigh the tree. Each comparison drops you one level. So the height of the tree — the longest root-to-leaf path — is the worst-case number of comparisons. And a binary (yes/no) tree of height h can hold at most 2ʰ leaves: 2 at depth 1, 4 at depth 2, doubling each level. Put the two facts together:

Read what just happened. We never named a specific algorithm. We said: whatever your comparison sort is — one you know, one you will invent, one no human has thought of yet — it is some decision tree, and every decision tree that sorts n items is at least log₂(n!) levels tall. That is why n log n is not "the best we have managed." It is the best that can exist. Merge sort already sits on that floor; you cannot pay less.

The numbers are concrete and I checked each one in Python. To sort 3 items you need at least ⌈log₂ 6⌉ = 3 comparisons; 5 items, at least 7; 12 items, at least 29; 100 items, at least 525. And log₂(n!) hugs n log₂ n so tightly that by a million items the floor is already 93% of it — same curve, same Θ(n log n) band, forever.

The floor only holds if you insist on comparing. What if the values could tell you where they belong — without a single comparison? →

Walk through the wall — counting sort

Suppose you are sorting a million song ratings, each an integer from 0 to 5. The comparison floor says n log₂ n ≈ 20 million questions. But you never need a question. A rating of 5 doesn't need to be compared with anything — it just is a 5, and you already know exactly where all the 5s go: after the 4s, before nothing. The value is its own address.

That is counting sort. Make one tally box per possible value. Walk the data once, dropping each item into its box. Then walk the boxes in order, pouring them back out. No item is ever weighed against another. Here it is, and it really runs:

def counting_sort(a, k):        # every value is an int in range 0..k-1
    count = [0] * k             # one tally box per possible value
    for x in a:                 # PASS 1 - n steps: tally each item
        count[x] += 1           #   the value IS the index. no comparison.
    out = []
    for v in range(k):          # PASS 2 - k steps: walk boxes in order
        out.extend([v] * count[v])   # pour box v back out, count[v] times
    return out

print(counting_sort([3,1,4,1,5,9,2,6,5,3,5,0,7,2,6], 10))
# [0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 9]   <- matches sorted()

Line by line: count = [0]*k builds k empty boxes. The first loop runs n times — count[x] += 1 uses the value x directly as an array index (Volume 1: indexing a list is O(1), a straight jump to a memory address). The second loop runs k times, emitting each value as many times as it was tallied. Total work: n + k. I ran it against Python's sorted() on the same data — identical output.

When k is small next to n, this is linear — it strolls under the comparison floor like it isn't there. I measured the op counts: a million items with values in 0–255 costs about 1,000,256 steps, where a comparison sort would spend ~20 million — roughly 20× fewer. There is no contradiction with the last section. The floor was proven for sorts that only compare. Counting sort never compares. Different game, different rules.

The price is written in the method. You need k boxes, so the values must be bounded integers (or things you can map to a small integer range) — you cannot counting-sort arbitrary floats or strings this way — and you pay O(k) memory for the boxes. Push k up toward "any 64-bit integer" and you would need billions of boxes; the trick collapses. Counting sort wins precisely when the range of values is small, whatever the count.

Bounded to 0–5 is easy. But a million distinct 9-digit ID numbers? That is k = a billion boxes. There is a way to keep the linear speed anyway — sort them one digit at a time. →

Radix sort — counting, one digit at a time

Big numbers break counting sort because their range is huge. But each individual digit has a tiny range — 0 to 9. So sort by the last digit, then the next, up to the first, using a stable counting sort on each pass. After the final digit, the whole list is sorted. This is radix sort, and it is exactly how the old punched-card machines physically sorted — a fact we'll come back to.

def radix_sort(a):
    m = max(a)
    exp = 1
    while m // exp > 0:              # one pass per digit of the biggest number
        a = counting_by_digit(a, exp)   # stable counting sort on this digit
        exp *= 10                    # move to the next digit up
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]   <- matches sorted()

The loop runs once per digit — call that d passes — and each pass is a counting sort over ten boxes, costing O(n + 10). Total: O(d·(n + 10)), which for fixed-width keys is just O(n). I ran it against sorted(); the outputs match. The whole thing works only because each pass is stable — it never disturbs the order the earlier passes established. That word, stable, is doing enormous quiet work here, and it deserves its own section next.

Everything in radix hangs on one promise: equal-keyed items keep their order across passes. Break that promise and the whole scheme scrambles. Time to make it precise. →

Stability — when equal keys must keep their order

A sort is stable if, when two items compare equal on the sort key, they come out in the same order they went in. Unstable sorts are free to shuffle ties. It sounds like a technicality. It is the difference between a spreadsheet that does what you meant and one that quietly corrupts your data.

Why it matters: it is how you sort by two keys. Say you want your playlist grouped by artist, and within each artist, ordered by length. Sort by the secondary key first (length), then by the primary key (artist) with a stable sort — the stable pass keeps the length-order intact inside each artist group. I ran exactly this:

songs = [("Levels","Avicii",200), ("Wake Me Up","Avicii",247),
         ("Titanium","Guetta",245), ("Without You","Guetta",210),
         ("Hey Brother","Avicii",254)]

step1 = sorted(songs, key=lambda s: s[2])   # first by seconds (secondary key)
step2 = sorted(step1, key=lambda s: s[1])   # then by artist (primary), STABLE

# ('Levels','Avicii',200) ('Wake Me Up','Avicii',247) ('Hey Brother','Avicii',254)
# ('Without You','Guetta',210) ('Titanium','Guetta',245)

Read the result: the Avicii block is internally sorted by seconds (200, 247, 254) and the Guetta block too (210, 245) — even though the second sort only looked at artist. The stable pass never touched the ties, so the first sort's work survived underneath it. Two stable sorts in a row give you a two-level ordering, for free. An unstable sort would have jumbled the seconds within each artist, and you'd have to sort with a compound key instead.

Python's sorted() is stable, and I have been leaning on that all chapter. But what is sorted()? It isn't plain merge sort. It is something cleverer — and it gets suspiciously fast on data that is already a bit sorted. →

What sorted() actually runs — Timsort

Real data is rarely random. Logs arrive almost in time order; a list you append to and re-sort is mostly sorted already; sensor readings drift. Timsort — the algorithm behind Python's list.sort() and sorted() — is built around that observation. It is a merge sort / insertion sort hybrid that first scans for runs: stretches already in order. Every run it finds is work it doesn't have to do. Then it merges the runs, using insertion sort to tidy short pieces and clever "galloping" to skip through long ones.

The consequence is dramatic, and I timed it on this machine (best of 5 runs, a million floats — treat the milliseconds as indicative, not exact):

n = 1_000_000                       # sorted() on different input orders
# random order    :  146.1 ms       <- the full n log n price
# already sorted  :    9.6 ms       <- ~15x faster: one giant run, near-linear
# reverse sorted  :   10.9 ms       <- ~13x faster: spots the descending run, flips it
# 20 sorted runs  :   10.6 ms       <- ~14x faster: merges 20 pre-made runs

On already-sorted data Timsort makes essentially one pass, confirms it is one long run, and stops — O(n), not O(n log n). Reverse-sorted is nearly as fast: it detects a strictly descending run and reverses it in place. This is why re-sorting a list you just tweaked is almost free. The general bound is O(n log r) where r is the number of runs — when the data is one big run (r = 1) that collapses to O(n); when it's fully scrambled (r ≈ n) you pay the full n log n. It never beats the comparison floor on random data — the last section forbids that — but it pockets every scrap of existing order.

Sorting arranges data so you can find things fast.

Sorting arranges data so you can find things fast — the next chapter is about the finding itself: searching & selection. How binary search pinpoints any item in a sorted array in O(log n) by halving the haystack instead of scanning it — and how the same halving idea plucks the median out of a billion numbers without ever sorting them. →

12Searching & selection — binary search is bigger than you think

Trace T23 stepped binary search line by line: two markers, one probe, half the list gone every time. This chapter is about what that little loop is really teaching you. First we nail the one idea that makes it correct — the invariant — and see why a three-line loop has bitten the best programmers alive. Then the reveal almost nobody learns as a beginner: you can binary-search things that aren't arrays at all. And finally quickselect — how to pull the median out of a billion numbers without ever sorting them. By the end you'll spot binary search hiding in problems that look nothing like search.

The invariant — the promise the loop never breaks

Binary search keeps three integers: lo, hi, and a scratch mid. That is the entire state — no copies of the list, whatever its size (O(1) extra space, as T23's memory panel showed). What makes the loop correct is a single sentence that is true before the loop, stays true after every pass, and is still true when it stops. That sentence is the loop invariant:

If the target is in the list at all, it is somewhere in the window [lo, hi].

Watch how each step defends it. You probe the midpoint. If arr[mid] is smaller than the target, then — because the list is sorted — every slot from lo up to and including mid is also too small. The target cannot be there. So you move lo = mid + 1: you threw away half the window and the promise still holds, because you only discarded slots you proved couldn't hold the target. The mirror move, hi = mid - 1, does the same on the other side. The window can only shrink, and it never sheds the answer.

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1          # invariant: answer, if present, is in [lo, hi]
    while lo <= hi:                    # window still holds at least one slot
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid                # found it
        elif arr[mid] < target:
            lo = mid + 1              # left half proven too small — discard it
        else:
            hi = mid - 1              # right half proven too big — discard it
    return -1                         # window emptied — the target was never here

Now derive the speed, don't quote it. Each pass replaces the window with one of its halves: n becomes n/2, then n/4, then n/8… How many halvings until only one slot is left? That is the number of times you can divide n by two before hitting 1 — the definition of log₂ n. So the loop runs at most about log₂ n times. Counting the real worst-case probes (a target just past the end, forcing the deepest possible search) confirms it exactly:

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

Read the last line and let it land: a billion sorted items, found in 30 comparisons. Multiply the data by a thousand and the work grows by ten. That is what living on the O(log n) curve (green's frugal cousin from the volume's opening chart) buys you — the search race in the Algorithms Lab lets you watch linear's counter blow past it live.

Three lines, one promise. So why did one of the field's most famous essays claim that almost no one writes them correctly? →

Why binary search is the bug that ate the industry

Jon Bentley, in Programming Pearls, famously reported that when he asked roomfuls of professional programmers to write a bug-free binary search, the great majority failed — a result widely repeated because it keeps coming true. The loop is tiny. The bugs hide in four tiny decisions: < versus <=, and mid versus mid ± 1 on each side. Get one wrong and the invariant tears. Here are two classic tears, run for real:

arr = [11, 22, 33, 44, 55]

# BUG A — write  lo = mid  instead of  lo = mid + 1
def bug_infinite(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: lo = mid       # <- forgets the +1
        else:                    hi = mid - 1
    return -1

# BUG B — write  while lo < hi  instead of  lo <= hi
def bug_misses(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:                               # <- a 1-slot window never gets checked
        mid = (lo + hi) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: lo = mid + 1
        else:                    hi = mid - 1
    return -1

Line by line on Bug A: search for 55. The window narrows to lo=3, hi=4; mid = (3+4)//2 = 3; arr[3]=44 < 55, so lo = mid = 3 — unchanged. Next pass: same lo, same hi, same mid, forever. Because mid rounds down, dropping the +1 lets lo get stuck on a slot it already rejected. The invariant said "discard mid"; the code kept it.

Bug B is subtler and nastier — it returns a confident wrong answer. Using lo < hi, the loop quits the instant the window shrinks to a single slot (lo == hi), without checking that slot. So any element that ends up alone in the final window is reported as absent. Here is what the two bugs actually print:

correct(arr, 55)      -> 4
bug_infinite(arr, 55) -> INFINITE LOOP (hit safety cap at 1000 iterations)

correct(arr, 55)      -> 4
bug_misses(arr, 55)   -> -1
bug_misses fails to find: [22, 55]

Bug B doesn't fail on 55 alone — it silently loses 22 too, and on a bigger array it loses a different scattered handful. No crash, no red. Just occasionally, quietly, the wrong answer. That is why binary search is legendary: the bugs don't announce themselves.

lo, hi = 1_500_000_000, 1_700_000_000   # both valid indices
true lo+hi            = 3200000000
as signed 32-bit int  = -1094967296     <- overflowed NEGATIVE
bad mid = (lo+hi)//2  = -547483648      <- negative index -> crash
safe mid = lo+(hi-lo)//2 = 1600000000   <- never overflows

You now own the loop cold. Time for the part they don't tell beginners: the array is optional. →

Binary-search the answer, not the array

Strip binary search down to what it truly needs. Not a list. Not even numbers-in-a-row. It needs exactly one thing: a yes/no question that is monotonic — once the answer flips to "yes," it stays "yes" for everything past that point. A sorted array is just one place that shows up ("is arr[i] ≥ target?" flips from no to yes exactly once). But any monotonic yes/no gives you the same superpower: binary-search the space of possible answers.

Here is the move on a problem with no array to search. A ship loads packages (in fixed order) off a conveyor; with a weight capacity C it takes some number of days. You must deliver everything within D days. What is the minimum capacity that still makes the deadline? Brute force would try every capacity from small to large. But notice the structure: a bigger ship is never worse — more capacity can only mean the same or fewer days. So "can we finish in D days with capacity C?" is monotonic in C: false, false, false, then true forever. We don't search packages; we binary-search the capacity.

weights = [1,2,3,4,5,6,7,8,9,10];  D = 5

def days_needed(cap):                 # simulate one candidate capacity — O(n)
    days, load = 1, 0
    for w in weights:
        if load + w > cap:            # this package won't fit today
            days += 1; load = 0       # start a new day
        load += w
    return days

def feasible(cap): return days_needed(cap) <= D    # the monotonic yes/no

lo, hi = max(weights), sum(weights)   # smallest sane cap … ship-it-all-in-a-day cap
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid        # mid works — the answer is mid or smaller
    else:             lo = mid + 1    # mid too small — need strictly more
answer = lo

Line by line: days_needed walks the packages once and counts the days a given capacity forces — that's the O(n) feasibility check. feasible wraps it into the monotonic question. The search bounds come from the problem itself: capacity can't be less than the heaviest single package (it must at least fit), and never needs to exceed the total (that ships everything in one day). Then the familiar loop — but over capacities, not indices. Watch it run:

search range [10, 55]  (46 possible capacities)
minimum feasible capacity = 15   (days it needs: 5)
feasibility checks performed = 5           <- vs up to 46 for a linear sweep

  window [10,55]  try C=32  -> 2 days  feasible=True
  window [10,32]  try C=21  -> 3 days  feasible=True
  window [10,21]  try C=15  -> 5 days  feasible=True
  window [10,15]  try C=12  -> 6 days  feasible=False
  window [13,15]  try C=14  -> 6 days  feasible=False

Five checks instead of forty-six, and it scales the same beautiful way: log₂(range) feasibility checks. The cost is O(n · log(range)) — the range can be astronomically large and you'd barely notice. The whole trick was spotting the monotonic yes/no and building bounds around it. Integer square root is the same idea in miniature: "is mid² ≤ n?" is monotonic in mid, so a hand-written isqrt(n) is a binary search on the answer — and it agrees with the standard library's math.isqrt right up to isqrt(10**18) = 1000000000.

Searching finds a value. What if you want a value by its rank — the median, the 90th percentile — out of a billion unsorted numbers? →

Quickselect — the median without sorting

The obvious way to get the median is to sort and grab the middle. But sorting does far more work than you asked for: it puts every element in order when you only wanted one position. That's O(n log n) to answer an O(n) question. Quickselect pays only for what you need.

It borrows quicksort's partition step (detailed in trace T28): pick a pivot, then rearrange so everything smaller sits left of it and everything larger sits right. After one partition the pivot is in its final sorted position — say index p — for free. Now the key difference from quicksort: quicksort recurses into both sides; quickselect looks at p, compares it to the rank k you want, and recurses into only the side that contains k. The other half is thrown away, unsorted, unexamined.

def quickselect(a, k):                 # k-th smallest, 0-indexed
    a = a[:]                           # copy; partition rearranges in place
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)       # pivot lands at its final index p
        if   p == k: break             # the pivot IS the k-th smallest — done
        elif p <  k: lo = p + 1         # k is to the RIGHT — discard the left
        else:        hi = p - 1        # k is to the LEFT  — discard the right
    return a[k]

Now count the work, don't quote it. The first partition scans all n elements. Then you keep one side — on average about half — so the next partition scans ~n/2, the next ~n/4, and so on. Sum it: n + n/2 + n/4 + … = 2n. A geometric series that converges — total work proportional to n, i.e. O(n) average. Sorting's recursion keeps both halves and never gets to drop that series; quickselect's "recurse one side" is exactly what collapses the log n factor. Measured on random data, the comparisons stay a flat constant-times-n no matter how big n gets:

median of [200, 90, 150, 60, 247, 245, 33]
  quickselect -> 150   (statistics.median -> 150)   using only 14 comparisons
  the list was never sorted

 n      : avg quickselect comparisons (median, 100 runs) : ratio to n
   1000 :         3322                                    : 3.32 x n
   2000 :         6631                                    : 3.32 x n
   8000 :        26319                                    : 3.29 x n
  16000 :        53182                                    : 3.32 x n

The ratio holds at ~3.3 regardless of n — the signature of linear growth. (The constant sits above the ideal 2 because a random pivot isn't a perfect median; still a constant.) For n = 16,000, that's about 53,000 comparisons versus roughly 223,000 for a full comparison sort — you got the median with a quarter of the work and never produced a sorted list you didn't want.

Fast, correct, frugal. Now — where does all this actually run, and what's the mental move to carry out of the chapter? →

The move to steal: turn problems into monotone questions

You already used binary search this week without noticing. When you run git bisect to find the commit that introduced a bug, git binary-searches your history: it checks out the middle commit, you say "good" or "bad," and half the timeline is eliminated — the same monotonic structure (once broken, stays broken) as the ship. A thousand commits, found in about ten checkouts. Debugging a long function by commenting out the first half to see if the bug survives? Same move. Bisection is the everyday face of binary search, and naming it makes you faster at it.

Selection shows up just as widely. Every time a dashboard shows you a p95 latency or a median income, something computed a rank statistic — and at scale it is not sorting billions of rows, it is quickselect or its streaming cousins (approximate-quantile sketches like t-digest). Database query planners lean on selectivity estimates to guess how many rows a filter keeps. "Give me the top 100 without ordering all ten million" is argpartition, not sort.

That is the 1% reframe hiding in this chapter. Beginners memorize "binary search = find a number in a sorted array." Engineers see the deeper shape: binary search is a tool for any monotone predicate, and selection is a tool for any rank — and both come from refusing to do more work than the question demands. Don't sort when you need one position. Don't scan when the structure is monotone. Ask what you actually need, then pay exactly that.

We've been searching straight lines and sorted ranges. But most real problems — maps, friend networks, web links, task dependencies — aren't lines at all; they're webs. Chapter 13 opens with the most general structure in all of computing: a graph, nothing but nodes and the edges between them — and the two ways to explore one that unlock GPS routing, PageRank, and six degrees of separation. →

13Graphs — the universal model

Almost every hard problem you will ever meet is secretly the same problem wearing a different costume. Roads, friendships, web links, task lists, molecules, the moves in a chess game — draw dots for the things and lines for the connections and they all become one shape: a graph. This chapter builds that shape from zero, shows the two ways a machine stores it, and hands you the three tools that answer almost every question you can ask of it — BFS (the ripple), DFS (the plunge), and Dijkstra (the weighted route). After it, your first move on a new problem changes forever: you will ask "what are the nodes, what are the edges?" — and half the difficulty will dissolve on the spot.

Dots and lines — the most general structure there is

A graph is just two sets. A set of nodes (also called vertices) — the things. And a set of edges — the connections between pairs of things. That is the entire definition. There is nothing else to it, and that emptiness is exactly why it is the most powerful idea in this volume: because we said nothing about what the things are, anything can be a node.

Cities are nodes and roads are edges. People are nodes and friendships are edges. Web pages are nodes and hyperlinks are edges. Tasks are nodes and "must-happen-before" is an edge. Atoms are nodes and chemical bonds are edges. The valid states of a Rubik's cube are nodes and a single twist is an edge. Every one of these is literally a graph — not "like" a graph, not "modelled as" a graph. Same structure, same algorithms, one skill.

Edges come in two flavours, and the distinction runs through the whole chapter. An undirected edge is a two-way street: if Ada is friends with Bex, Bex is friends with Ada. A directed edge points one way: page A links to page B, but B need not link back; "socks before shoes" does not mean "shoes before socks". And an edge can carry a weight — a number attached to the connection: the minutes to drive that road, the cost of that flight, the strength of that bond. No weight means every edge is worth the same; weights are where Dijkstra will earn its keep.

We have the picture. But a machine cannot store a picture — it stores bytes. So the first real question is brutally practical: how do you write a graph down? →

Two ways to write a graph down — and the tradeoff that decides everything

There are two honest ways to hand a graph to a computer, and choosing between them is the first engineering decision of every graph problem.

The adjacency list: for each node, store a list of its neighbours. Ada → [Bex, Cy]; Bex → [Ada, Dot, Eli]; and so on. In Python this is just a dictionary of lists — a hash table (Volume 1) whose values are dynamic arrays. To find Ada's neighbours you jump straight to her list; to store the whole graph you spend one slot per node plus one slot per edge-endpoint. Count it: V nodes and E edges cost V + 2E slots for an undirected graph (each edge appears at both of its ends). That is O(V + E) space — you pay only for connections that actually exist.

The adjacency matrix: a V×V grid of 0s and 1s, where cell [i][j] = 1 means "there is an edge from i to j". Want to know if Ada and Fin are directly connected? Read one cell — O(1), instant, no scanning a list. But the grid has V² cells whether or not the edges exist, so it costs O(V²) space no matter how few edges there are. The matrix reserves a box for every possible connection in the universe; the list writes down only the ones that are real.

That difference is not academic — it is the difference between fitting in memory and not. Real graphs are sparse: a person has hundreds of friends, not millions; a web page links to dozens of pages, not billions. Here is the gap, computed for a million users each with about ten friends:

V = 1_000_000        # a million users
avg_deg = 10         # ~10 friends each
E = V * avg_deg // 2 # undirected edges  -> 5,000,000

matrix_cells = V * V           # 1,000,000,000,000  (a trillion)
list_slots   = V + 2 * E       #        11,000,000  (eleven million)
print(matrix_cells // list_slots, "x bigger")   # -> 90909 x bigger

Line by line: V and avg_deg set the scale; E works out the edge count (halved because each friendship is one edge shared by two people). matrix_cells is V² — a trillion boxes. list_slots is V + 2E — eleven million. The matrix is ~90,909× larger. Even packed to a single bit per cell, that trillion-cell matrix is 125 GB just to record who-knows-whom; the list fits in a few hundred megabytes. For a sparse graph, the matrix is a catastrophe you can measure.

Now the graph is in memory. The real magic starts: asking it questions. The first and most human question — "what's the shortest way from here to there?" — is answered by dropping a stone in a pond. →

BFS — the ripple that finds the shortest path

Drop a stone in still water and a ring spreads outward. Every point the ring touches at the same instant is the same distance from the splash. Breadth-first search (BFS) is exactly that ring, run on a graph: start at a node, visit all its neighbours (distance 1), then their unvisited neighbours (distance 2), then theirs (distance 3), rippling outward one layer at a time until the whole graph is soaked.

The engine that makes the ripple stay a ring is a queue — the first-in-first-out line from Volume 1. You add newly-discovered nodes to the back and always process from the front. Because the front always holds the earliest-discovered (nearest) node, you finish an entire distance-layer before the next one begins. Watch it run on a tiny friendship network:

from collections import deque
def bfs(graph, start):
    dist = {start: 0}                 # how many hops from start
    q = deque([start])                # the ripple's frontier (a queue)
    while q:
        u = q.popleft()               # take the NEAREST unfinished node
        for v in graph[u]:            # look at each neighbour
            if v not in dist:         # first time we reach v...
                dist[v] = dist[u] + 1 # ...so this IS its shortest distance
                q.append(v)           # add it to the back of the line
    return dist

print(bfs(friends, "Ada"))
# -> {'Ada': 0, 'Bex': 1, 'Cy': 1, 'Dot': 2, 'Eli': 2, 'Fin': 3}

Line by line: dist doubles as "have I seen this node?" and "how far is it?". q starts holding only the source. Each loop takes the front node u — guaranteed to be the nearest unfinished one — and scans its neighbours. The load-bearing line is if v not in dist: the first time BFS reaches a node is along the shortest possible route, because every shorter route would have arrived in an earlier ring. So dist[v] = dist[u] + 1 is not a guess — it is the final answer, set once and never revised. The run confirms it: Ada→Fin is 3 hops, and no path is shorter.

Now stop reading and run the ripple yourself. Below, BFS spreads across a grid with walls. Press Step and watch the wavefront fan out ring by ring, colouring each cell by its distance, until it reaches the goal — and the shortest path falls out. Then flip to DFS and watch the very same search abandon the rings and plunge into one corridor instead.

You just watched BFS spread and DFS plunge on the same maze. That "plunge" is not a bug — it is a second superpower, and it happens to be one line of code away. →

DFS — the plunge, and the one-line secret it shares with BFS

Depth-first search (DFS) picks a direction and commits: from a node it walks to a neighbour, then a neighbour of that, going as deep as it can before it hits a dead end and backs up to try the last unexplored turn. Where BFS fans out in careful rings, DFS dives to the bottom first. Its natural engine is the stack — last-in-first-out — which is also why DFS is usually written as a plain recursive function: the call stack from Volume 1 is the stack.

Here is the insight that makes graph search click, and it is one of the most satisfying in the whole volume. BFS and DFS are the same algorithm. The only difference is which end of the frontier you take the next node from. Take from the front (a queue) and you get rings — BFS. Take from the back (a stack) and you get a plunge — DFS. One line changes:

def traverse(graph, start, use_stack):
    seen = {start}; frontier = deque([start]); order = []
    while frontier:
        u = frontier.pop() if use_stack else frontier.popleft()   # <-- the ONLY difference
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v); frontier.append(v)
    return order

print(traverse(friends, "Ada", False))  # queue -> ['Ada','Bex','Cy','Dot','Eli','Fin']
print(traverse(friends, "Ada", True))   # stack -> ['Ada','Cy','Eli','Fin','Dot','Bex']

Line by line: the setup is identical for both. The whole personality of the search lives in one expression — frontier.pop() (take from the back, LIFO, a stack) versus frontier.popleft() (take from the front, FIFO, a queue). Swap it and nothing else, and the same code produces two utterly different explorations: the queue visits Ada's world layer by layer; the stack shoots straight down one chain to Fin before it ever finishes with Bex. That is the deep unity — search is just "keep a frontier and choose whom to expand next"; the data structure is the strategy.

The crown jewel of DFS is topological sort: given tasks with "must-come-before" dependencies (a directed graph), produce an order in which every task appears after everything it depends on. Course prerequisites, spreadsheet cell recalculation, and — most famously — build systems and package managers all live or die by it. Run it on a course catalogue:

# prereqs: a course maps to the courses it requires first
print(toposort(prereqs))
# -> ['Intro', 'DataStruct', 'OS', 'Algorithms', 'Databases', 'Compilers']

prereqs["Intro"] = ["Compilers"]   # make Intro depend on Compilers -> a loop
print(toposort(prereqs))           # -> None   (no valid order exists)

The first call returns a legal study plan: Intro before everything, Compilers dead last because it needs both Algorithms and OS. The second call is the important one. Once we make Intro require Compilers — which requires Algorithms, which requires DataStruct, which requires Intro — there is a cycle, and no ordering can satisfy it. The algorithm returns None. That is not a failure; it is the exact error your build tool throws when two packages depend on each other, or your spreadsheet flags a circular reference. Topological sort's ability to say "impossible, and here's why" is why it sits at the heart of make, npm, pip, and every CI pipeline.

Dijkstra — shortest paths when the edges have a price

The moment edges carry weights, BFS breaks. Its whole guarantee rested on "one hop = one unit", so the first arrival was the nearest. With weights, a path of three cheap edges can beat a path of one expensive edge, and the ripple — which counts hops — walks right past the better route. We need a search that expands by total distance so far, not by hop count. That search is Dijkstra's algorithm.

The idea is greedy (chapter 8): keep a frontier of "reached but not yet finalised" nodes, each tagged with the cheapest total distance found to it so far, and always finalise the globally cheapest one next. Because all weights are positive, once a node is the cheapest on the frontier, nothing discovered later can undercut it — so its distance is locked. To repeatedly pull out the current minimum, Dijkstra leans on a priority queue, a.k.a. a min-heap: treat it as a black box (its internals are a later volume) that hands back the smallest item in O(log n). Watch it route a commute where minutes, not turns, are the currency:

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]                 # min-heap of (distance_so_far, node)
    settled = {}
    while pq:
        d, u = heapq.heappop(pq)      # the globally CHEAPEST open node
        if u in settled: continue     # already finalised -> skip stale copy
        settled[u] = d                # lock it in: this is its shortest distance
        for v, w in graph[u]:         # relax each outgoing edge
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return settled

print(dijkstra(roads, "Home"))
# -> {'Home': 0, 'B': 1, 'A': 3, 'C': 4, 'Work': 7}

Line by line: dist holds the best-known tentative distance to each node; pq is the min-heap frontier, seeded with the start at distance 0. Each loop pops the cheapest open node — heappop is the black-box min — and, if it hasn't already been finalised, settles it: its distance is now final and correct. Then it relaxes every outgoing edge: "could I reach v more cheaply by going through u?" If yes, it records the shorter distance and pushes v back onto the heap. The gem is in the output. The direct road Home→A costs 4, but Dijkstra reports A's distance as 3 — because the detour Home→B→A is only 1+2. The greedy frontier found the sneaky cheaper route the eye would skip, and Work comes out at 7 (Home→B→A→C→Work).

How costly is all this? Count the work. Every node is settled once, and each settling relaxes its outgoing edges — so across the whole run we touch each edge once, doing an O(log V) heap operation per touch. That is O(E log V) for the edges, plus O(V log V) for the pops, giving Dijkstra's classic O((V + E) log V). On a continent-sized road graph that is the difference between a route in milliseconds and one that never returns.

BFS, DFS, Dijkstra — three questions, three tools, one structure. The last step is the one that changes you as an engineer: learning to see the graph that was hiding inside the problem all along. →

The move that makes you dangerous — model it as a graph first

Step back and look at what just happened across this chapter. A friendship network, a maze, a course catalogue, and a road map are, on the surface, four unrelated things. We solved all four with the same three functions, unchanged, because underneath they were the same object: nodes and edges. That is the real lesson of this chapter, and it is worth more than any single algorithm.

The transferable move — the one the top 1% make almost reflexively — is this: when a new problem lands, before you write a line, ask "what are the nodes, and what are the edges?" The answer is often startling. States of a puzzle are nodes; legal moves are edges; "solve the puzzle" becomes "find a path" — and BFS solves a sliding-tile puzzle for free. Words are nodes; "differ by one letter" is an edge; word-ladder puzzles and spell-check suggestions become shortest paths. Jobs and machines are nodes; "can run on" is an edge; scheduling becomes a matching problem. Half of algorithm design is not inventing a clever method — it is recognising the graph that was there the whole time, at which point a solved, off-the-shelf algorithm takes over.

One human made a piece of this feel inevitable. Edsger Dijkstra later recounted that he worked his shortest-path method out in about twenty minutes in 1956 — in his head, sitting at a café, with no paper and no computer. The lesson isn't the biography; it's the way of thinking it reveals. He didn't picture streets. He pictured the pure structure — nodes, edges, a growing frontier of "cheapest settled so far" — and reasoned about that. When you strip a problem down to its skeleton like that, the answer often stands up on its own. That stripping-down is the skill this whole chapter was really teaching.

We just found the shortest path through a graph in polynomial time — fast, reliable, done. So here is a question that sounds almost identical: instead of the shortest path from Home to Work, find the shortest tour that visits every city and returns — the Travelling Salesman. Change that one word, "path" to "tour", and every fast algorithm we own detonates: the cost curve leaps off the polynomial track and onto the red O(2ⁿ) explosion, where a few dozen cities would outlast the universe.

We found the shortest path in polynomial time — fast, reliable, done. The next chapter switches tools entirely: strings & number theory, the crypto-and-quant layer. How Ctrl-F, git diff and DNA aligners find a pattern without re-reading what they already know — and the one impossibly one-sided calculation that hides behind every padlock icon in your browser. →

14Strings & number theory — the crypto and quant layer

Two toolkits that punch far above their weight. String search is how spell-check, git diff, DNA aligners and Ctrl-F find a needle in a haystack — and the trick is refusing to re-read what you already know. Number theory is the quiet machinery under every padlock icon in your browser: primes, remainders, and one impossibly one-sided calculation. After this chapter you'll derive why the naive scan is slow and how to fix it, sieve every prime up to a million by pure elimination, raise a number to the millionth power in about twenty multiplications, and see exactly why a TLS handshake is safe.

The naive scan re-reads what it already knows

You want to find a short pattern inside a long text. The obvious method: line the pattern up at position 0, compare character by character; on a mismatch, shift the pattern one step right and start comparing again from scratch. It works. Let's count what it costs — because counting operations, not guessing, is the whole game (chapter 0).

Let the text be length n and the pattern length m. At each of the n − m + 1 starting positions we might compare up to m characters. Multiply: the worst case is (n − m + 1) · m comparisons — that's O(n·m). The friendly case looks fine — searching "cat" in "the cat sat on the mat" takes just 22 comparisons, because most alignments fail on the very first letter. The trap is text that almost matches everywhere.

def naive_search(text, pat):
    n, m = len(text), len(pat)
    comps = 0
    for i in range(n - m + 1):        # every start position
        j = 0
        while j < m:                  # compare pattern left to right
            comps += 1
            if text[i+j] != pat[j]:
                break                 # mismatch: give up, shift by 1
            j += 1
    return comps

print(naive_search("aaaaaaaaaaaaaaaaaaaab", "aaaab"))  # 85
print(naive_search("the cat sat on the mat", "cat"))    # 22

Line 4 walks every start position; line 6 compares until a mismatch. The pathological string "a"×20 + "b" against "aaaab" costs 85 comparisons (verified) — at each of 17 positions it matches four as, then fails on the b, and throws all four matches away. Push it to a 10,001-character run with a length-100 pattern and the count explodes to 990,200. The waste has a name, and naming it is the engineer's move (chapter 4): we keep re-reading text characters we already looked at.

If we already matched four as, we know the next window starts with three as. Why look again →

KMP: never re-examine a matched character

Here is the insight that Knuth, Morris and Pratt turned into an algorithm around 1970 — and you can feel it without the machinery. When the pattern aaaab matches four as and fails on the b, those four matched characters are not garbage — they are information. They tell you the text here is aaaa…, so the next plausible alignment already has three as satisfied. There is no reason to walk the text pointer backwards. Ever.

KMP precomputes, from the pattern alone, a small table: "if I fail after matching k characters, how many are still guaranteed to match at the next useful shift?" That table lets the text pointer march forward and never retreat. Each text character is looked at essentially once, so the whole search is O(n + m) — the n to scan the text plus the m to build the table. Linear. The nested loop collapses into a single pass.

# same haystack and needle as before, counting TEXT-character reads
naive : 85 reads     KMP : 21 reads     (text length = 21)
naive : 990,200      KMP : 10,001       (text length = 10,001)

# the pattern's "memory" table (how much prefix survives a mismatch)
lps("aaaab") == [0, 1, 2, 3, 0]
lps("abcab") == [0, 0, 0, 1, 2]

Those numbers are measured, not asserted. KMP reads each of the 21 text characters exactly once; the naive scan read 85. On the big string it is 10,001 versus 990,200 — a gap that widens forever as the text grows. The lps table is the pattern's self-knowledge: for aaaab, after matching aaaa we can keep 3 characters on the next shift; that [0,1,2,3,0] is the "don't look back" rule, baked in ahead of time.

Rabin-Karp: slide a hash over the text

Different idea, same enemy (re-work). Instead of comparing characters, fingerprint them. Turn every length-m chunk of text into a single number — a hash (chapter 6) — and turn the pattern into a number too. If two numbers differ, the chunks differ; you skip the comparison entirely. The catch: computing a fresh hash for every window would itself be O(m) per window, O(n·m) total — no win. The move that saves it is a rolling hash: when the window slides one step, don't recompute — update. Subtract the character leaving the left, shift, add the character entering the right. That's O(1) per slide, O(n) for the whole text.

Think of the window's hash as a number written in base 256 (one digit per byte). Sliding right is exactly like turning 734 into 345: drop the leading digit's place value, multiply by the base, add the new trailing digit — all modulo a big prime so the number stays small.

BASE, MOD = 256, 1_000_000_007
high = pow(BASE, m-1, MOD)             # place value of the leftmost char
h = hash_of(text[:m])                  # hash of the first window
# slide from window i to i+1 in O(1):
h = ((h - ord(text[i])*high) * BASE + ord(text[i+m])) % MOD
#     - drop the leaving char --  -shift-  - add the entering char -

Ran on "the cat sat on the mat" searching "cat": the pattern hashes to 6513012, the window slides 19 times, and — this is the honesty check — every single rolling update was compared against a hash computed from scratch and matched exactly. The match is reported at index 4, the same spot the naive scan found. Where a hash collides (two different chunks, same fingerprint), you fall back to a direct character check, so a collision costs a little time but never a wrong answer.

String search leaned on hashing and modular arithmetic — mod a big prime. That "mod" is the doorway to number theory, and it starts with the oldest algorithm still in daily use →

Euclid and clock arithmetic

Modular arithmetic is clock math: on a 12-hour clock, 10 + 5 = 3, because you wrap around after 12. Write it 15 mod 12 = 3. That wrap-around is the entire foundation of what follows — remainders, not full numbers, are what cryptography computes with, because they stay small and they hide information.

The greatest common divisor (GCD) of two numbers is the largest number dividing both. The naive way — test every candidate down from the smaller number — is O(min(a,b)). Euclid's insight, over two thousand years old and still unbeaten, is one line: any divisor of a and b also divides their remainder a mod b. So replace the bigger number with that remainder and repeat; the numbers shrink fast, and when one hits zero the other is your answer. You stepped this in trace T33 — here's why it's fast.

def gcd(a, b):
    while b:                 # until nothing is left over
        a, b = b, a % b      # shrink: replace (a,b) with (b, remainder)
    return a

gcd(1071, 462)      # 21, reached in 3 steps
gcd(832040, 514229) # 1,  worst case: 28 steps (consecutive Fibonacci numbers)

Line 3 is the whole algorithm: each step throws away the larger number entirely and keeps only the remainder. How fast do the numbers shrink? Each two steps at least halves the larger value, so the step count is O(log(min(a,b))) — logarithmic, like binary search (chapter 1). The measured worst case is telling: feed it two consecutive Fibonacci numbers and every step peels off exactly one — gcd(832040, 514229) takes 28 steps. Fibonacci is the slowest possible input, and even that is tiny. Python's built-in math.gcd runs this same idea.

Remainders let us tame huge numbers. The next tool uses nothing but a wrap-around and a crossing-out pencil to find every prime there is →

The Sieve of Eratosthenes — primes from pure elimination

A prime is a number with no divisors but 1 and itself — the atoms of arithmetic, and the raw material of crypto. To find every prime up to n, you could test each number for primality one at a time. Eratosthenes, a librarian in ancient Alexandria, had a lazier and faster idea: don't hunt for primes — eliminate non-primes. Write every number from 2 to n. Take 2, keep it, and cross out every multiple of 2. Move to the next number still standing (3), keep it, cross out every multiple of 3. The next survivor (5), same. Whatever is never crossed out is prime, because a composite number is by definition a multiple of some smaller prime.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:                 # stop at √n — see below
        if is_prime[p]:
            for k in range(p*p, n+1, p):  # cross out p², p²+p, p²+2p, …
                is_prime[k] = False
        p += 1
    return [i for i in range(n+1) if is_prime[i]]

sieve(30)   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Two small optimizations carry real weight. Line 5 stops at √n: any composite ≤ n has a factor no larger than its square root, so once you've sieved with primes up to √n, everything left is prime. Line 7 starts crossing at p², not 2p: smaller multiples of p (like 2p, 3p) were already crossed by smaller primes. The cost is startling — O(n log log n), which grows so slowly that log log n is under 4 for any n you'll ever sieve. Measured: π(1,000,000) = 78,498 primes, found in one sweep.

Fast modular exponentiation — the engine of crypto

Cryptography constantly computes a^b mod m where a, b, and m are numbers hundreds of digits long. Compute a^b the obvious way — multiply a by itself b times — and you'd need b − 1 multiplications, and the intermediate number would have billions of digits. Both are fatal. Two ideas fix it. First, reduce mod m after every multiply, so the number never grows past m. Second, square, don't multiply one-by-one — the divide-and-conquer trick from chapter 5. To get a^13, write 13 in binary as 1101: a^13 = a^8 · a^4 · a^1. You get a, a², a⁴, a⁸ by repeated squaring — one multiply each — and combine the ones whose bit is set.

def modpow(a, b, m):
    result = 1
    a %= m
    while b > 0:
        if b & 1:                     # this bit of the exponent is set
            result = (result * a) % m # …so fold a's current power in
        a = (a * a) % m               # square: a → a² → a⁴ → a⁸ …
        b >>= 1                        # drop that bit
    return result

modpow(7, 13, 11)          # 2       — matches Python's built-in pow(7,13,11)
modpow(2, 1_000_000, 1_000_000_007)   # done in ~20 squarings, not a million

The loop runs once per bit of the exponent, so it does about log₂(b) squarings — O(log b). Measured: 7^13 mod 11 takes 4 squarings and 3 multiplies (7 operations) instead of 12, and every result matches Python's built-in pow(a, b, m), which is this algorithm. The showstopper: 2^1,000,000 mod (10⁹+7) — a naive approach wants 999,999 multiplications; this does 20 squarings and 7 multiplies. Twenty-seven operations to raise 2 to the millionth power. That single collapse from a million to twenty is what makes public-key cryptography physically possible.

Fast modular power plus big primes is almost the whole recipe for the padlock in your address bar. Time to assemble it →

RSA: why big primes keep your secrets

Here's the asymmetry everything rests on. Multiplying two large primes is trivial — p × q = n, instant. Going backwards — given only n, recover p and q — has no known fast method; the best algorithms take astronomically long for numbers a few hundred digits wide. A one-way street: easy forward, effectively impossible back. That gap is a trapdoor, and RSA is built on it. First you need big primes, and here trial division dies: checking a 19-digit number like 2⁶¹−1 took about 70 seconds on this machine, while the probabilistic Miller-Rabin test — which asks a few clever "if this were prime, this equation would hold" questions using fast modular power — answered in roughly a ten-thousandth of a second (a gap of order a half-million-fold here; timings vary by machine). Miller-Rabin says "almost certainly prime," and you can drive the error probability below the chance of a cosmic ray flipping your answer. You'll meet the randomness behind it in chapter 15.

p, q = 61, 53                 # (real RSA uses ~300-digit primes)
n   = p * q                   # 3233   — public
phi = (p-1) * (q-1)           # 3120   — secret, needs p and q
e   = 17                      # public exponent
d   = pow(e, -1, phi)         # 2753   — private key (modular inverse of e)

c = pow(65, e, n)             # encrypt message 65 → 2790   (public key)
m = pow(c, d, n)              # decrypt 2790      → 65     (private key)

Line by line: n = 3233 is public and e = 17 is public — together they're the padlock anyone can snap shut. The private key d = 2753 is the modular inverse of e (the number that undoes it, mod φ), and computing φ = 3120 requires knowing p and q. Encrypting is one fast modular power: 65^17 mod 3233 = 2790. Decrypting is another: 2790^2753 mod 3233 = 65 — the original, back exactly (verified). An attacker sees n, e, and the ciphertext 2790, but to get d they must factor n — and that's the wall. Every ingredient is from this chapter: big primes (Miller-Rabin), the encrypt/decrypt operations (fast modular power), and the key (modular inverse via Euclid).

Miller-Rabin only worked by flipping a coin — it trusts randomness to be almost-certainly right, fast. That's not a hack; it's a whole design philosophy. Chapter 15 makes randomness your armor: a random pivot that defeats any adversary, and estimating answers you can't compute by throwing darts →

15Randomization & the probabilistic mind

Every chapter so far made choices deterministic — the pivot, the hash, the next node. Now flip one coin. This chapter shows why deliberately adding randomness makes an algorithm faster, safer, and able to answer questions no exact method can touch. After it you'll be able to armor a sort against its own worst case, compute a number like π by throwing darts, price a financial option by simulating the future, and draw a perfectly fair sample from a stream far too big to store.

Every fixed plan has a nemesis

A deterministic algorithm always makes the same choice on the same input. Usually that's a virtue. But it hides a nasty consequence: the algorithm has a fixed worst case — one specific arrangement of input that drives it to its slowest possible behavior. And if someone can read your code — it's open-source, or a public API, or a well-known library — they can construct that exact arrangement and feed it to you on purpose.

Quicksort is the classic victim. Tell it "always pick the first element as the pivot," then hand it an already-sorted list. Every partition peels off just one element, the recursion sinks n levels deep, and the tidy O(n log n) collapses into O(n²). (You stepped quicksort's partition in trace T28 — here we attack it.) That's not a thought experiment; it's a denial-of-service. Put a naive quicksort behind a web endpoint and an attacker who sends sorted data can pin your CPU with a tiny request.

The escape is not a cleverer fixed rule — the adversary just studies the new rule and defeats it too. The escape is to stop being predictable. If the algorithm flips a coin to make its choices, there is no single input that is reliably its worst case, because the worst case now depends on coins the attacker cannot see.

So how much does a single coin flip actually buy? Let's stop asserting and start counting →

Randomness is armor — the randomized pivot

Count the fixed-pivot disaster first. Partitioning a block of m elements costs m−1 comparisons. If every pivot is the extreme value — exactly what a sorted list guarantees — the block sizes march down n−1, n−2, …, 1, and the total is (n−1)+(n−2)+…+1 = n(n−1)/2. That's the textbook O(n²), and it is not approximate: I ran a comparison-counting quicksort on a sorted list of n = 2000, and the fixed-pivot version reported 1,999,000 comparisons — precisely n(n−1)/2, to the comparison.

Now make the pivot random. Each pivot is equally likely to be any rank, so partitions are balanced on average, and the expected number of comparisons works out to about 2n ln n (≈ 1.39·n·log₂n) — squarely the O(n log n) class. Same sorted input, random pivot: about 24,600 comparisons, averaged over twenty runs. Roughly 80× fewer — on the very input that murdered the deterministic version.

The deep move: we didn't change the input, we changed who chooses. The chance that a random shuffle happens to land on any one specific bad arrangement is 1/n!. For a mere 20 items that's 1 in 2.4×10¹⁸; for a shuffled deck of 52 cards it's 1 in 8×10⁶⁷ — more arrangements than there are atoms in the galaxy. The worst case didn't vanish. It became something you will not witness before the heat death of the universe.

def quicksort_count(a, pivot="first"):
    a = list(a); comps = 0; stack = [(0, len(a)-1)]
    while stack:
        lo, hi = stack.pop()
        if lo >= hi: continue
        if pivot == "random":                 # ← the one line that armors it
            p = random.randint(lo, hi); a[p], a[hi] = a[hi], a[p]
        pv = a[hi]; i = lo
        for j in range(lo, hi):
            comps += 1                         # count every key comparison
            if a[j] < pv:
                a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        stack.append((lo, i-1)); stack.append((i+1, hi))
    return comps
# sorted input, n=2000:  fixed → 1,999,000   random → ~24,600  (≈80× fewer)

Line by line: we sort a copy with an explicit stack instead of recursion, so the sorted worst case can't overflow Python's call stack. The if pivot == "random" line swaps a randomly chosen element into the pivot slot — that's the entire defense. The inner for loop is the partition, and comps += 1 tallies each key comparison so we measure cost directly instead of trusting a formula. Everything else is ordinary Lomuto partitioning (stepped in T28).

Armor is one use of a coin. The other is stranger: using randomness to compute a number you can't otherwise reach →

Compute by throwing darts — Monte Carlo

Now turn the idea inside out. Instead of using randomness to protect an exact algorithm, use it to estimate an answer that's hard to compute directly. The technique is called Monte Carlo — after the casino — and its motto is: to learn about a system, sample random outcomes from it and count.

The cleanest demonstration computes π. Draw a 1×1 square, and inside it the quarter of a circle of radius 1 centered at one corner. The square's area is 1; the quarter-circle's area is (1/4)·π·r² = π/4. Throw darts uniformly at random into the square. The fraction that land inside the quarter circle must, on average, equal the ratio of the areas — π/4. So π ≈ 4 × (darts inside) / (total darts). A dart at (x, y) is inside exactly when x² + y² ≤ 1 — one multiply, one compare, no trigonometry, and the symbol π appears nowhere in the code. You measure it by counting.

def estimate_pi(n):
    inside = 0
    for _ in range(n):
        x, y = random.random(), random.random()   # a dart in the unit square
        if x*x + y*y <= 1.0:                        # inside the quarter circle?
            inside += 1
    return 4 * inside / n                           # fraction inside ≈ π/4

#      n         estimate      error
#     100        3.120000     0.021593
#    1000        3.128000     0.013593
#   10000        3.126000     0.015593   ← note: WORSE than n=1000!
#  100000        3.137280     0.004313
# 1000000        3.140592     0.001001
# 10000000       3.142310     0.000717

Four lines do it. random.random() draws a coordinate in [0,1), so (x, y) is a uniform dart. The one comparison x*x + y*y <= 1.0 asks "is it inside?", inside tallies the hits, and 4 * inside / n turns the ratio into π. The table is a real run — and look closely: at n = 10,000 the estimate was actually worse than at n = 1,000. That's not a bug. A single random run can get lucky or unlucky. What improves reliably is never one run — it's the typical error, and pinning that down is the next section.

The √N law — and pricing the future

Here's the law that governs every Monte Carlo estimate, and it's worth burning into memory: the typical error shrinks like 1/√N, where N is the number of samples. I measured it directly. Run the π estimator 200 times at N = 100 and the estimates scatter with a standard deviation of about 0.165. Quadruple to N = 400 and the scatter halves to 0.081. Quadruple again to 1600 → 0.039; again to 6400 → 0.020. Every ×4 in samples halves the error — the fingerprint of 1/√N.

Flip that around and it stings: to win one more correct decimal digit — 10× smaller error — you need 100× more samples. Monte Carlo hands you the first digits cheaply and charges brutally for the last ones. Why 1/√N? Each sample is an independent draw, and averaging N independent draws is exactly the setup where the spread of the average narrows as 1/√N — the same statistics that make a poll of 1,000 people accurate to a few percent, not a few thousandths. It isn't special to π; it's the signature of averaging independent randomness.

And this is exactly why Wall Street runs on Monte Carlo. The fair price of a financial option is an expected value — the average payoff across every possible future path of the underlying stock, discounted back to today. For the simplest options there's a closed-form answer (the Black–Scholes formula). For the messy real ones — path-dependent, many assets, exotic payoffs — the integral has no formula at all. So you don't solve it; you sample it: simulate thousands of random futures, compute the payoff in each, and average. I priced a European call both ways. Black–Scholes says 10.4506. Monte Carlo, averaging simulated futures: 1,000 paths → 11.02, 100,000 paths → 10.49, a million paths → 10.4458 — the √N law crawling toward the true price. Risk desks simulate millions of paths every night to answer "how much could we lose tomorrow?" That is expected-value thinking made computational: when you cannot reason about the average, sample it.

def mc_call(n, S0, K, r, sigma, T):
    drift = (r - 0.5*sigma**2)*T
    vol   = sigma*(T**0.5)
    total = 0.0
    for _ in range(n):
        z  = random.gauss(0, 1)               # one random shock
        ST = S0*math.exp(drift + vol*z)        # one simulated future price
        total += max(ST - K, 0.0)              # the call's payoff on that path
    return math.exp(-r*T) * total/n            # discounted average payoff
# Black–Scholes = 10.4506;  mc_call(1_000_000) → 10.4458

The loop is the whole idea: random.gauss(0, 1) draws one random "shock", S0*exp(drift + vol·z) turns it into one possible price at expiry, and max(ST − K, 0) is what the call pays on that future. Average over a million futures, discount to today, and you've evaluated an integral no one wrote down — by sampling it.

Quicksort's coins and π's darts gamble in opposite directions. Naming that difference is the whole taxonomy of randomized algorithms →

Two ways to gamble — Las Vegas vs Monte Carlo

Look at what the coins actually put at risk. Randomized quicksort always returns a correctly sorted list — the coins only affect how long it takes; a bad streak makes it slower, never wrong. The π estimator is the mirror image: it always finishes in exactly N steps, but the answer is only approximate — a bad streak makes it wrong-ish, never slow. Those are the two families of randomized algorithm, and knowing which one you're holding tells you exactly what can go wrong.

The beautiful bridge between them: if you can check an answer cheaply, you can convert Monte Carlo into Las Vegas. Guess with a fast randomized method, verify the guess; if it's wrong, guess again. The verify step turns "probably right" into "definitely right, eventually" — you've traded a small error probability for a small extra runtime.

A fair sample from an endless stream — reservoir sampling

The problem sounds impossible. You're watching a firehose — every tweet, every log line, every sensor reading — and you want to keep a uniformly random sample of, say, one item, such that when the stream finally ends, every item that ever flowed past had an equal chance of being the one you kept. The catch: you don't know how long the stream is (it could be billions of items, or never end), you get exactly one pass, and you have O(1) memory — room for the one item, nothing more.

The solution is one line of genius. Reservoir sampling: keep the first item. When the i-th item arrives, replace whatever you're holding with it with probability exactly 1/i. That's the entire algorithm — and notice that n, the stream's length, never appears.

def reservoir_one(stream):
    kept = None
    for i, item in enumerate(stream, start=1):   # i = 1, 2, 3, ...
        if random.random() < 1.0 / i:            # newest barges in w.p. 1/i
            kept = item
    return kept
# length-10 stream, 1,000,000 trials — how often each item was the survivor:
#   item 0: 10.00%   item 1: 10.04%   item 2:  9.98%   item 3:  9.99%
#   item 4:  9.97%   item 5: 10.00%   item 6: 10.06%   item 7:  9.98%  ...
# every item ≈ 1/10, dead fair — with room for exactly one item in memory

The loop reads one item at a time. At position i, random.random() < 1.0/i is true with probability 1/i — so item 1 is kept for sure, item 2 has a 1-in-2 shot at bumping it, item 3 a 1-in-3 shot, and so on. The comment is a real million-trial run: every one of the ten items ended up the survivor almost exactly a tenth of the time, deviating by at most 0.06 percentage points. Perfectly fair, in one pass, in constant memory.

Here's the magic, worked out. Consider item i. It gets kept at step i with probability 1/i. To still be the survivor at the end, it must then not be replaced by items i+1, i+2, …, n. Item j replaces with probability 1/j, so it fails to replace with probability (j−1)/j. Multiply the whole chain of survival:

(1/i) · (i/(i+1)) · ((i+1)/(i+2)) · … · ((n−1)/n) = 1/n

and it telescopes — every numerator cancels the denominator before it — leaving exactly 1/n. Every item, whether it arrived first or billionth, ends with probability 1/n. The math is fair by construction, and n is never needed.

Step back and see the shape of this whole chapter. Randomness bought three different things: armor (no adversary can aim at a random pivot), computation (sample the darts, the futures, the light rays — and average your way to an answer no formula gives), and fairness under ignorance (a uniform sample without ever knowing how much there is). The transferable move — the one the 1% run on reflex — is this: when being predictable is your weakness, add a coin; when the exact answer is out of reach, estimate it by trying many random cases and averaging; and when you want a property like fairness, work backwards from the property to the rule that produces it. Stanislaw Ulam invented Monte Carlo not by out-computing the neutron equations but by asking a humbler question — recovering from illness and playing solitaire, he wondered about his odds of winning, and realized that instead of grinding through the combinatorics he could just deal many random hands and count. That question — "what if I just try it thousands of times and count?" — is available to you on every hard problem you'll ever meet.

Six chapters of patterns; one volume of thinking. Next we assemble them into a single operating system for the algorithmic mind — how to look at any new problem and know, in seconds, which technique it wants. Chapter 16 is the difference between the 99% and the 1%, and it closes the volume →

16How to think like the 1%

This chapter teaches no new algorithm. It teaches the thing underneath all of them — the operating system for an algorithmic mind, the small set of reflexes that turn fifteen chapters of techniques into one way of seeing. The gap between a programmer whose code melts under load and one whose code scales to a billion users is not a bigger memory or a faster brain. It is a loop, run so many times it became instinct. By the end of this chapter you will be able to sit in front of a problem you have never seen, and know exactly what to ask, what to reach for, and how to tell whether your fix actually worked — the whole volume, folded into a way of thinking you can carry anywhere.

Derive it — never memorize it

The single worst way to learn this material is to memorize a table of "sorting is n log n, hashing is O(1)." Memorized facts rot, and they teach you nothing about the problem in front of you that isn't already in the table. The 1% do the opposite: they derive the complexity on the spot, by counting the work as the input grows — exactly the move you built in Chapter 1. The growth zoo isn't a list to recite; it's a lens you look through. And there's a shortcut that makes the derivation almost mechanical: count the operations at some size n, then again at 2n, and look at the ratio.

def quad(n):                 # a full nested loop
    ops = 0
    for i in range(n):
        for j in range(n):
            ops += 1
    return ops

for n in (1000, 2000, 4000, 8000):
    print(n, quad(n))
# 1000 1000000   |  double n -> 4x the work
# 2000 4000000   |  ratio 4  ->  the exponent is 2
# 4000 16000000  |  ratio 4  ->  O(n squared)
# 8000 64000000  |  ratio 4

Read it line by line. quad just tallies how many times the inner body runs. We call it at four sizes, each double the last, and print the count. The counts we actually got were 1,000,000 then 4,000,000 then 16,000,000 then 64,000,000 — every time we doubled n, the work went up four-fold. That ratio is the answer: doubling the input and getting 4× the work means cost ∝ n², because 4 = 2². You never had to remember that nested loops are quadratic — you watched the exponent fall out of the ratio. Run the same probe on six different shapes and the ratios sort themselves into the whole zoo:

So you can name any single function's growth on sight. But real work isn't "name this loop" — it's "I have a problem; which tool do I even reach for?" That needs a different reflex →

The toolkit is a flowchart, not a menu

Beginners keep algorithms in a list and scan it hopefully. Experts keep them in a decision tree keyed on the signature of the problem — a handful of tell-tale features that each point straight at a technique. Learn the triggers, not just the tools. Here is the whole volume compressed into that tree: read the problem, spot the signature, follow the arrow.

The tree tells you what to reach for. But what do you do before you know the answer — when nothing in the tree obviously fits? You run the loop →

The loop that cracks a problem you've never seen

Here is the method that survives contact with the unknown — the four-beat cycle from Chapter 4, now as your default operating procedure. One: solve it the dumbest way that works — brute force, no cleverness, just a correct answer. Two: measure the baseline — count its operations, name its Big-O. Three: ask the one question that unlocks everything — where is the wasted work? Look for the thing you compute again and again, the search you redo, the pair you re-examine. Four: kill that waste with a technique from the tree, then re-check the complexity to confirm the curve actually dropped. Then loop.

Watch it turn on a problem you've already met. Two-sum: find two numbers in a list that add to a target. Beat one, brute force: check every pair — two nested loops, and the doubling probe from earlier would report ratio 4, so it's O(n²). Beat three, the question: what work repeats? For each number x you re-scan the whole list looking for target − x — you keep asking "is this value present?" over and over. Beat four: that exact phrase — "have I seen the value I need?" — is a trigger in the tree, and it points at hashing (ch6). Store each number in a set as you pass it; the lookup becomes O(1); the whole thing collapses to O(n). One pass through the loop turned a quadratic into a linear. You didn't need to be clever — you needed to be systematic. (Step it live in trace T30.)

The loop drops your Big-O. But two programs with the same Big-O can still finish minutes apart. To win there, you have to think about the metal →

Respect the constant — machine sympathy

Big-O is necessary, not sufficient. It deliberately throws away the constant factor — and once you've picked the right curve, that discarded constant is the entire remaining game. Two algorithms at the same O(n) can differ by 5× or 50× depending on how kindly they treat the machine from Volume 1: whether the data they walk is already in the CPU's fast cache, whether the branches they take are predictable, whether the work can spread across cores. Here are two pairs, each with identical Big-O, timed on this machine:

data = list(range(5_000_000))

# both O(n): sum by hand vs. the built-in
def manual():
    t = 0
    for x in data: t += x
    return t

def sum_data(): return sum(data)
from timeit import Timer
def best(f): return min(Timer(f).repeat(repeat=5, number=1)) * 1e3   # ms, best of 5

print("manual loop:", round(best(manual), 1), "ms")   # ~113 ms (same Big-O)
print("builtin sum:", round(best(sum_data), 1), "ms")  # ~16 ms  (~7x faster)

Both loops touch all five million items exactly once — flatly, provably O(n); the doubling probe gives ratio 2 for each. Yet on this run the hand-written loop took about 113 ms and the built-in sum() about 16 ms — roughly 7× apart at the same complexity (wall-clock on one machine; your numbers will differ, but the ordering won't). The gap is pure constant: the interpreter re-dispatches Python bytecode on every pass of the hand loop, while sum() runs the same additions in a tight C loop with far less overhead per element. Same curve, very different constant. The second pair shows the memory hierarchy directly:

grid = [[1]*2000 for _ in range(2000)]   # 4,000,000 cells

def row_major():           # walk each row fully before the next
    s = 0
    for r in range(2000):
        row = grid[r]
        for c in range(2000): s += row[c]
    return s
# row-major: 131 ms   |   col-major (swap the loops): 200 ms  -> ~1.5x, same O(R·C)

Both nested loops visit all four million cells — identical O(R·C). But row_major walks memory the way it's laid out: it grabs one row (a contiguous run of references) and marches straight along it, so the values it needs next are already sitting in cache. Swap the loops to go column-first and every single step jumps to a different row-list, defeating the cache and costing about 1.5× more here (131 ms vs 200 ms) for the very same additions. In pure Python the interpreter dilutes the effect; in the C or Rust underneath your libraries the same swap can cost 5–10×. The Big-O saw none of this — the machine saw all of it.

That's the engineering. But the deepest payoff of this whole volume is that the reflexes work off the computer entirely — on your errands, your bugs, your decisions →

Run the loop on your life

The reason these ideas feel powerful is that they were never really about code. They're about structure, and structure is everywhere. Once the reflexes are in, you start applying them without noticing — which is the real "you use this every day" moment.

import math
# BINARY-SEARCH your debugging: a bug appeared somewhere in your commit history.
# "good before, broken after" is monotonic -> bisect it, don't read every commit.
for commits in (100, 1000, 100_000, 1_000_000):
    print(commits, "commits ->", math.ceil(math.log2(commits)), "checks")
# 100 -> 7   |   1000 -> 10   |   100000 -> 17   |   1000000 -> 20

That's git bisect, and it's Chapter 12 wearing overalls. A million commits hide a bug; reading them one by one is O(n) — a million checkouts. But "works before the bad commit, fails after" is monotonic, and monotonic is a trigger for binary search: test the middle, throw away half, repeat. We computed it — 20 checks, not a million. That's O(log n) applied to your own workflow, and it's why "bisect it" is the fastest debugging advice anyone will ever give you. The other techniques transfer just as cleanly:

# EXPECTED-VALUE your risks (quant thinking for life): train vs. drive.
p_delay, delay = 0.10, 40         # 10% chance the train loses 40 minutes
train = 25 + p_delay * delay      # base 25 min + expected delay
drive = 35                        # flat, "safe"
print(round(train,1), "vs", drive)   # 29.0 vs 35  -> take the "risky" train

The train feels risky because of that 40-minute tail. But expected value — probability × cost — puts the delay at just 0.10 × 40 = 4 minutes, so the train averages 29 minutes against the drive's 35. The "safe" choice was slower. That's the quant's core move (Chapter 15): don't react to the scary outcome, weight it by its probability. And the rest fold in the same way — greedy your errands (visit the nearest stop next, ch8), hash your memory (write it down so recall is O(1) instead of re-deriving it, ch6), and DP your decisions (never re-solve a problem you've already solved — cache the answer, ch9).

So how do you drill these until they're automatic — until you see in growth curves and triggers without trying? →

The gap is a loop, run relentlessly

Here is the honest, slightly deflating, deeply encouraging truth this volume has been building toward: the distance between the 99% and the 1% is not talent. It is not a gift you were or weren't born with. It is this handful of reflexes, practiced until they became how you see — and reflexes are trainable. Five drills turn the ideas in this book into instinct:

• Derive the complexity of everything you read. Every function in every codebase, every snippet in every article — before you move on, count its work and name its Big-O. Make it a tic. This is how "what's the growth?" becomes automatic.
• Re-derive one classic a day, from scratch. Binary search, merge sort, the two-sum trick — rebuild one each morning without looking. You'll discover how much you'd only memorized, and each rebuild files it deeper as a method, not a fact.
• Explain it out loud. If you can't say why quicksort is n log n on average to an imaginary beginner, you don't own it yet. Teaching is the fastest debugger for your own understanding.
• Always solve, then optimize. Get a correct brute-force answer first — every single time — then run the loop. Cleverness before correctness is how you ship fast, wrong code.
• Ask the two questions, on everything. What is the input size? Where is the wasted work? Those two questions, asked reflexively, are the bulk of what separates the engineer from the coder.