02You'd Be Doing the Same Work Twice

Page 1 closed by pointing at a floor built out of counting — one bit per question, and no cleverness gets under it. That floor is page 3's whole business; set it down for one page, because there is a ceiling worth seeing first and it is much stranger.

The thirtieth Fibonacci number is 832,040.

Here is the procedure almost everyone writes first. If n is 0 or 1, hand back n. Otherwise hand back fib(n−1) + fib(n−2). One comparison, two subtractions, one addition — and every one of those is a single machine instruction.

A loop reaches 832,040 in twenty-nine additions.
The recursion reaches it in 2,692,537 calls.

Now look at what those calls are doing, because it is stranger than it is slow. Every call that reaches the bottom hands back a 1 or a 0, and the answer is nothing but those handed-back values added together. Exactly 832,040 of them hand back 1. The procedure computes 832,040 by counting to it, one at a time.

So the running time is not close to the answer and it is not proportional to the answer. It is the answer. And it belongs to no line: take the most expensive operation in the entire procedure and make it free, and the call count does not move by one. Slowness is not a property of lines. It is a property of how the calls are arranged — and there are only four things anyone can do to an arrangement.

01Not one line of it is slow

Draw the calls and the waste stops being a feeling and becomes a countable object. fib(30) calls fib(29) and fib(28). Each of those calls two more. The calls form a tree, and every branch of it ends at a call that hands back 1 or 0. That tree has 1,346,269 endpoints (F(31)) — the 832,040 ones and 514,229 zeros the answer is assembled from. Every call that is not an endpoint makes exactly two more, so the non-endpoint calls number one fewer than the endpoints — 1,346,268 of them. And the whole tree is 2,692,537 calls (1,346,269 + 1,346,268). And here is the part that should irritate you. Those 2,692,537 calls carry only 31 different questions between them — fib(30), fib(29), on down to fib(0). fib(2) alone is asked 514,229 separate times (F(29)), and it works out the same 1 on every one of them.

The call count is not merely large. It is the next Fibonacci number, doubled: computing fib(n) takes 2F(n+1) − 1 calls — 2 × 1,346,269 − 1. So the tree grows at exactly the rate of the numbers it is producing. Fibonacci numbers grow by a factor of 1.618 per step (φ, the golden ratio), and so, therefore, does the work.

Add 1.44 to n and the work doubles (log 2 ÷ log 1.618 = 1.44).
Add 10 to n and it multiplies by 123 (1.618¹⁰ = 123).

So fib(40) costs 331 million calls (2F(41) − 1), and fib(90) costs 9.3 quintillion (2F(91) − 1) — 295 years at a billion calls a second (9.3×10¹⁸ ÷ 10⁹ seconds). The loop version of fib(90) does 89 additions and is finished before you lift your finger off the key. That is the effect worth naming and it has nothing to do with Fibonacci: every line in the procedure adds, and the arrangement of those lines multiplies. Local addition, global exponentiation.

Which brings us to the claim I just made — slowness is not a property of lines — and you can check it rather than take it. Count every elementary operation the whole run performs. One comparison per call, so 2,692,537 comparisons. Two subtractions and one addition per call that is not an endpoint, so 2,692,536 subtractions and 1,346,268 additions. One handed-back base value per endpoint, so 1,346,269 of those. Total: 8,077,610 operations, which is three per call, one short (3 × 2,692,537 − 1). And the one short is the one extra endpoint. A tree whose calls come in twos or not at all always has exactly one more endpoint than internal call. Notice what that bill charges for: arithmetic, with the call itself free. That is a convention, not a fact, and Fig. 1 adopts the other one — it bills three units for the machinery of calling on top of the arithmetic, so its totals run larger and its three-per-call comes out even. Two bills, both right, because they answer two different questions — and noticing which question you are answering is most of this skill. Now attack it. Pick the single most expensive operation in the procedure — the comparison, which is a third of the entire bill — and make it cost nothing. The bill falls to 5,385,073 (8,077,610 − 2,692,537), and the tree still contains 2,692,537 calls. You just deleted a third of the work and moved the call count by zero. Page 1 already told you why that had to happen: time is step count multiplied by cost per step, and a line is only ever cost per step. Every line-level saving available here is a discount on the number 3.

You cannot make total work smaller by doing the same work faster. That is the constraint this page is built on, and the heading is the commonest way it bites: you'd be doing the same work twice, and no amount of speed makes the second time free. Page 1 already priced everything you can buy — it is all a discount on cost per step — and no discount has ever removed a call. Only four moves change the total, and I mean four families rather than four tricks; everything I know of that genuinely reduces work is one of them or a combination of them. Each is bought with a different currency, and the currency is the interesting part.

Rearrange it — same answers, differently shaped tree. Paid for in design insight.
Share it — work out fib(2) once and hand that same 1 to all 514,229 askers. Paid for in memory.
Skip it — prove that some best answer already agrees with the move you are about to make, and never examine the alternatives at all. Paid for in proof.
Postpone it — leave the work undone until a moment when it happens to be cheap. Paid for in patience.

Those four are the four sections that finish this page, in that order, and nothing else on it is a fifth option.

Before you can choose a move, though, you have to have the arrangement written down, and there is a standard sheet for that with exactly four entries on it. All four are read straight off the code, and none of them requires a thought. How many recursive calls does one call make? How much smaller is each one? What does it cost before the calls? What does it cost after them? Read those off a halving sort — two calls, each on half, nothing to do before, and one pass over n items to merge afterwards. You have written T(n) = 2T(n/2) + n without deciding anything. Read them off binary search and you get T(n) = T(n/2) + 1. Read them off the Fibonacci procedure and you get T(n) = T(n−1) + T(n−2) + 1, that last +1 being the single addition at the bottom of the line. Notice that the sheet's last two entries add: their sum is the f(n) it carries. That is why a partitioning sort writes down the same 2T(n/2) + n as the halving sort. The partitioning sort spends its n splitting before the calls, and the halving sort spends it merging after. The sheet cannot tell those two apart, and does not need to. This is the reversal people trip over: producing a recurrence is clerical, and solving one is where all the thinking lives. Nobody needs to be clever to write the sheet. They need to be clever to read the total off it.

And the sheet has a domain, which is the sentence most courses leave out. The standard recipe — the master theorem, which you will meet by name in a moment — is written for the form a·T(n/b) + f(n). There is a slot for how many pieces, and a slot for divided by how much. There is nowhere on it to write "minus one." Fibonacci subtracts rather than divides, and that single difference is the entire exponential. Halving 30 reaches 1 in five steps (log₂ of 30 ≈ 4.9). Subtracting 1 from 30 takes thirty. Both procedures make two calls at every step, so both trees branch by two. One of them has five levels to branch across; the other has thirty, which is precisely the room that 1.618-per-step needed to run in. Put real counts on it: a halving procedure on 30 items makes 59 calls in total (2 × 30 − 1), and fib(30) makes 2,692,537. Depth is the exponent, and depth is decided by whether you divide or subtract — one character of the procedure, and the only character that mattered.

So the waste has a shape, and the shape is countable: 2,692,537 calls asking 31 distinct questions, at three operations each, not one of which is slow. Nothing on that list is a defect you could find by reading lines, which is exactly why reading lines is the wrong instrument. The right instrument is the drawing — and the next section is about reading an answer off one, including for the two recurrences the master theorem looks at and declines.

02Read the answer off the drawing

A recursion tree is not a picture of the calls. It is an invoice, and it has one line per level. Take the halving sort whose sheet we just filled in — T(n) = 2T(n/2) + n — and hand it 64 items.

The root merges all 64.
Level 1 is two nodes merging 32 each, which is 64.
Level 2 is four nodes merging 16 each, which is 64.
Level 6 is sixty-four nodes holding 1 each — and there is nothing there to merge.

Every merging row bills the same 64, because doubling the node count and halving the piece cancel each other exactly. Six rows merge — six halvings to take 64 down to 1 (log₂ 64 = 6) — so the sort moves 384 elements (6 × 64), which is the number the procedure in Fig. 2 was caught moving. The recurrence, though, is charging for slightly more than moving. f(n) = n is the work at a node of size n, so at a leaf it is f(1) = 1 — the call arriving, checking its own size, returning. Sixty-four leaves, sixty-four units, a seventh row. Bill that row too and the total is 448 (7 × 64), the same 448 the closed form hands you (n lg n + n = 384 + 64). Both are right, and the gap between them is exactly the leaf count: 384 is what the machine moves, 448 is what the recurrence costs. Every drawing from here on bills all seven rows, because f is charged at every node and a leaf is still a node. And the habit worth stealing is not the number. It is saying which one you are counting before you add anything up. None of that was about sorting. Level j holds a^j nodes and each one costs f(n/b^j); multiply across a row, then add the rows. That is the entire method. No cases, no theorem, nothing to remember.

Which lets me defuse the one piece of notation that makes people close the tab. n^(log_b a) is not notation. It is a headcount — it is the number of leaves, and you can count them yourself. Every node has a children, and the tree runs log_b n levels deep, so the bottom row holds a multiplied by itself that many times. Make it concrete: three children, each on half the input, at n = 64. The tree is six levels deep (log₂ 64 = 6), so the bottom row holds 729 leaves (3⁶). Now evaluate the frightening expression: 64 raised to log₂ 3, which is 64^1.585, which is 729. Same number, counted two ways — once by walking down the tree multiplying by three, once by insisting on writing that count as a power of n. The odd exponent 1.585 is not a fudge factor. It is what "three children on half-size pieces" looks like when you force it into that shape. And for the halving sort, where a and b are both 2, the exponent is 1 and the leaf count is n itself — 64 leaves, which the drawing already showed you.

Now bolt the two together and the three-case cookbook falls out of your hand rather than into your memory. A row's total is its node count times its per-node cost — a^j · f(n/b^j). When the per-node cost is a power of the piece size, which covers nearly everything you meet (f = x⁰, x¹, x²…), that row total is exactly n^p · (a/b^p)^j. Read what that says: each row is the row above it multiplied by a fixed number, and that number is a/b^p. The rows form a geometric series, and a geometric series can only do three things, so there are only three verdicts. Write the row totals down the margin as a column of bars and the shape tells you which one you are in.

Bars shrinking — 2T(n/2) + n², ratio 0.5: rows of 4096, 2048, 1024, 512, 256, 128, 64. The bill is 8,128 and the root alone paid 4,096 of it. Top-heavy: the root wins, and the total can never be more than twice the root, at any n.
Bars level — 2T(n/2) + n, ratio exactly 1: seven rows of 64. Flat. Nobody wins, which turns out to be its own verdict.
Bars growing — 3T(n/2) + n, ratio 1.5: rows of 64, 96, 144, 216, 324, 486, 729. The bill is 2,059 and the bottom row alone paid 729. Bottom-heavy: the leaves win, and the total can never be more than three times the leaf row, at any n.

You do not choose between three cases. You compute one number and look at the bars.

The middle verdict is the one worth staring at, because it is where every n log n you have ever seen comes from, and there is no magic in it. When the rows are level, the total is one row multiplied by the number of rows. That is 64 × 7, and the log in n log n is nothing but a row count — the number of times you can halve before you run out of input. Now watch that same flat profile answer a recurrence the master theorem will not even look at. Split into a third and two-thirds instead of two halves: T(n) = T(n/3) + T(2n/3) + n. There is no single b to write on the sheet, so the theorem has no slot to put it in and declines before it starts. Draw it anyway. The two children's pieces add back up to the parent's piece, so every row still totals n — the same level bars as before. The only thing that changed is that the rows now end ragged. The leftmost path divides by 3 each step and bottoms out early, and the rightmost path only multiplies by two-thirds and runs on much longer. At n = 1,000 the short path runs 6.3 levels deep (log 1000 ÷ log 3) and the long one runs 17 (log 1000 ÷ log 1.5). Every row still bills 1,000, so the total sits between 6,300 and 17,000, and n lg n is 9,970. Both ends of that bracket are a constant multiple of n log n. So the answer is n log n. The cookbook refused. The drawing shrugged.

The second refusal is worse, because the theorem looks straight at the recurrence and still returns nothing. T(n) = 2T(n/2) + n·lg n — a halving split where the combine is a bit more than a pass. The leaf count is n, and n lg n is plainly bigger than n, so the root should win and case 3 should fire. It does not, and the reason is a single clause: case 3 wants the combine to be polynomially bigger. Bigger than n^1.000001, or bigger than n to any fixed power you care to name. A stray lg n is not that. Case 2 wants the combine to be n exactly, and n lg n is not that either. The recurrence falls between two cases and the theorem shrugs back. So draw it: row j has 2^j nodes of size 64/2^j, each costing its size times the log of its size. The row totals 64(6 − j) — rows of 384, 320, 256, 192, 128, 64. Those rows are not geometric at all; they come down by subtraction, not by a ratio. Add them: 1,344 (64 × 21), which in general is n·lg n·(lg n + 1)/2 — that is Θ(n lg²n), a whole extra log worse than the halving sort. An answer, off a drawing, for a recurrence with no case.

And now the fact that explains the gap, and with it the two lines of the master theorem that look most like arbitrary small print. A shrinking series adds up to a constant times its first term only if it shrinks by a FIXED ratio. Fixed — not merely decreasing. Watch the fixed ratio fail in slow motion in the recurrence above. Row to row, the totals fall by (lg n − j − 1)/(lg n − j). At 64 items the first drop is a factor of 0.83 (320 ÷ 384). At a million items it is 0.95 (19 ÷ 20). At n = 2¹⁰⁰ it is 0.99. The top of the tree flattens out as n grows, and flat rows mean the row count starts to matter again. Put money on it: the total is 3.5 times the root at 64 items (1,344 ÷ 384), 10.5 times at a million, 50.5 times at 2¹⁰⁰ ((lg n + 1) ÷ 2). No constant covers 50.5, and no constant covers it in general, because the multiplier keeps climbing — which is exactly the claim case 3 would have made. "Polynomially bigger" is the clause that buys the fixed ratio. The regularity condition is the same requirement stated from the other side. a·f(n/b) ≤ c·f(n) with c below 1 says, in the tree's own language, the next row is at most c times this one. It was never small print. It was the drawing's one load-bearing assumption, written as a hypothesis.

Two things every drawing above quietly assumed, and I would rather declare them than let you catch them. First, nothing divides evenly. Halve 100 with rounding and the sizes run 100, 50, 25, 13, 7, 4, 2, 1, where exact halving would have said 12.5, 6.25, 3.125. Every size is off by less than one item, and it stays off by less than one item forever, because the next halving eats the drift as fast as rounding creates it. The halving count lands on 7 where the ideal wanted 6.64 (log₂ 100) — under one extra halving, on an invoice whose rows are already shrinking geometrically. But the honest half of that: proving something for exact powers of b and asserting it for every n is a real debt, not a free pass. The general proof exists, it is careful bookkeeping rather than a new idea, and I am telling you I skipped it rather than hoping you assume I didn't. Second, sometimes the argument does not shrink by a factor at all — it shrinks in the exponent. T(n) = 2T(√n) + lg n has no b anywhere, because nothing is ever divided by anything. So change the ruler and measure in bits. Square-rooting 65,536 gives 256, then 16, then 4 — as powers of two, 2¹⁶ → 2⁸ → 2⁴ → 2² — so the exponent goes 16 → 8 → 4 → 2. Square-rooting is halving, once you count in bits. Put m = lg n and the recurrence becomes S(m) = 2S(m/2) + m — the flat case, the same 448-shaped drawing. So the bill is 80 at n = 65,536 (16 × 4 + 16), and Θ(lg n · lg lg n) in general. The method was halving all along; the ruler was wrong. Which leaves the one thing the drawing will not do for you. It prices an arrangement; it never says which part of it to change. And a row total is only ever how many nodes multiplied by what each node costs — two knobs, no others. The next section is about which knob actually moves the bill, which one everybody grabs first, and the row where you should stop drawing the tree altogether.

03Delete a call, don't cheapen the combine

Everybody grabs the same knob — what each node costs — and it is the wrong one, so let me put a hard ceiling on what it can ever buy. It gets grabbed because it is the only part you can see on screen: the merge loop, the copy, the addition. Page 1 showed the ceiling in miniature — a binary search that cut comparisons 29-fold and moved the running time 24% — and here it is with the arithmetic at its cleanest. To multiply two n×n matrices straight from the definition, cut each one into four quarter-size blocks. Every output block is a sum of two block products. So a single call makes eight block multiplications and four block additions — T(n) = 8T(n/2) + n². At n = 1024 that tree bottoms out in 1,073,741,824 single-number multiplications (8¹⁰ = 1024³), and every addition on every row above them adds up to 1,072,693,248 (n³ − n²). The additions are half the bill. So pull that knob as hard as it goes — make every addition free. Not faster. Free.

The bill halves. Then it stops. Two times is the ceiling on that knob, at every n, forever.

Now the other knob: delete one call. Seven block multiplications instead of eight, nothing else touched. At n = 1024 the bottom row falls to 282,475,249 (7¹⁰), which is 3.8 times fewer ((8/7)¹⁰). At n = 4096 it is 4.96 times fewer ((8/7)¹²). And it never stops widening, because that a is reapplied on every level and levels multiply. There is the whole asymmetry in one line: the notation eats every constant that multiplies and never the constant that branches. Which makes the design rule blunt — count recursive calls, not lines of code.

Strassen, 1969, is that rule cashed in, and the price he paid is the part worth studying. He found a way to get all four output blocks out of seven half-size products instead of eight. And it costs him eighteen block additions where the ordinary method needed four. His combine is four and a half times more expensive (18 ÷ 4). He wins anyway, and you already know exactly why: the 4.5 multiplies the combine and is spent once, while seven instead of eight is a branch factor that reapplies on every level. The exponent moves from 3.000 to 2.807 (log₂ 7 = 2.8074), and every doubling of n widens the gap by another factor of 8/7. Now the rider, because I would rather say it than let you feel stupid later. Those seven products are a discovery, not a derivation. You can verify the identity in ten minutes — expand both sides, watch the terms cancel. But nobody can show you the reasoning that produces seven, because there is none on record. It was found, by search and by nerve. The same question one size up is still open: for 3×3 blocks the best anyone has ever found is 23 multiplications, nobody has ruled out 22, and that has been true since 1976. A page that hands you Strassen's seven as though they fell out of an argument is not teaching you. It is performing.

So take the sibling you can derive, because it is the identical move with a proof you can hold in one hand. Multiply two complex numbers: (a+bi)(c+di) = (ac − bd) + (ad + bc)i. Four real multiplications, and it looks like the floor. It is not. Work out three products instead — p = ac, q = bd, r = (a+b)(c+d). The real part is p − q, straight off the definition. And r expands to ac + ad + bc + bd, so r − p − q leaves ad + bc — the imaginary part. Three lines, one multiplication deleted, paid for with three extra additions (5 against 2). Now aim that at a recursion. To multiply two 1024-digit numbers, split each down the middle: x = x₁·10⁵¹² + x₀. The product needs x₁y₁, x₀y₀ and the middle term x₁y₀ + x₀y₁. That is four half-size multiplications, T(n) = 4T(n/2) + n. And the bottom row holds 1,048,576 single-digit products (4¹⁰, which is 1024²). You have rebuilt long multiplication exactly and gained nothing. Now apply the trick: the middle term is (x₁+x₀)(y₁+y₀) − x₁y₁ − x₀y₀, and the two things being subtracted are the two products you already have. Three multiplications, T(n) = 3T(n/2) + n, bottom row 59,049 (3¹⁰). Same two numbers, 17.8 times fewer digit products ((4/3)¹⁰), and an exponent of 1.585 (log₂ 3) where school arithmetic sits at 2.

That is the first question — can I delete a call? — and it only ever gets asked if recursion is available at all, which brings the second. Recursion pays when the sub-thing is literally the same thing, and real splits leak. Take a million price ticks and find the buy tick and the sell tick with the largest gain between them. Brute force prices every pair: 500 billion candidates (10⁶ × 999,999 ÷ 2), which is eight minutes at a billion a second. Now try to ask it by halves and feel it leak. Best pair in the left half, best pair in the right half — and then the winner turns out to buy on the left and sell on the right. The two half-answers have nothing to say about it. A pair of far-apart values does not add. So change what you measure until it does: work on the tick-to-tick differences instead of the prices. A buy-and-sell window is now a contiguous run of differences, and its value is their sum — and sums add across a seam, which is the exact property we were hunting. Then the honest half, which is where people oversell this move: the reframe buys nothing at all. You are still staring at 500 billion candidate ranges and the same eight minutes. A reformulation is a permission slip, not a speedup.

Now spend the permission, and notice that one question does the design and the arithmetic at the same time: what crosses my seam, and what does it cost? Split the differences down the middle. Any winning range is entirely in the left half, entirely in the right half, or straddling the midpoint — no fourth option exists, which is why the split is safe. Two of those three come back free from the recursion. The third is not the same problem in miniature; it is a different and much easier one, because it is pinned: it must contain the seam. So walk leftward from the seam keeping the best running total, walk rightward from the seam keeping the best running total, add the two. Two passes, n operations — and that number is not an afterthought, it is the f(n) on the sheet. T(n) = 2T(n/2) + n, level bars, the flat verdict: 20 million operations at a million ticks (10⁶ × lg 10⁶ = 19.9M) against 500 billion pairs. 25,000 times less work, and eight minutes becomes a fiftieth of a second. The reframe was the permission. The split was the entire win.

And once a quantity adds across a seam, the cheapest version of this move opens up: it can ride along on a divide-and-conquer you were already paying for. Page 1 measured disorder as inversions — pairs sitting in the wrong order relative to each other. Counting them by the definition means looking at every pair. So a hundred thousand log lines cost 5 billion checks (10⁵ × 99,999 ÷ 2) — five seconds of a machine's life to answer one diagnostic question. But inversions add: the total is left plus right plus crossing, and the merge step of a halving sort is already walking both halves in order. So watch it fall out for nothing. The merge takes an item from the right half while k items are still unspent on the left. That item is smaller than every one of those k, and therefore inverted with all of them. Add k and carry on merging. No extra pass, no extra data structure, one accumulator. The five seconds become 1.7 milliseconds (10⁵ × lg 10⁵ = 1.66M), 3,000 times cheaper, and the sorted list drops out of the same run as a souvenir.

Two honest closes, and the first one is free money: the size of the output is a lower bound nobody has to prove. Multiplying two n×n matrices means physically writing 1,048,576 answers at n = 1024 (1024²), so no method beats Ω(n²), ever, and you knew that before considering a single method. Between that floor and Strassen's 2.807 the exponent has been coming down since 1969, and it has never reached 2. The current published record is just above 2.37. If your textbook prints 2.376 it is quoting a 1990 result that has been beaten several times since. Now the second close. Nobody runs those record-holders. Their hidden constants are so enormous that the crossover sits past any matrix that has ever existed. That is the general fact underneath it: "asymptotically faster" is a claim about large n, and the size where it starts being true is computable. Two costs on a piece of k items. The quadratic method charges roughly a·k per item, and the halving method roughly b·lg k per item. So they trade places exactly where k / lg k = b/a. Measure the ratio — page 1 already warned you that growth rates tell you a crossover exists and never where it is. A measured ratio of 4 gives 16 on the nose (16 ÷ lg 16 = 4). That is why the C++ standard library's sort stops recursing at sixteen items and finishes with insertion sort. Page 1's deliberately brutal ratio of 25 (50 against 2) puts the same equation at 189. Strassen obeys the identical algebra. Taken all the way down to 1×1 blocks it is 4.7% worse than the ordinary method at n = 512, and only 8% better at 1024. That is why every real implementation stops at a block size and calls the ordinary multiply.

So, three questions, in order, before you optimise anything recursive.

Can I delete a call?
What crosses my seam, and what does it cost?
Where do I stop recursing? — computed, never copied out of somebody's library.

Every move in this section left the tree standing and changed its shape. Not one of them noticed that fib(2) is still being worked out 514,229 separate times, which is the next section's business entirely.

04The tree was a graph the whole time

So look at that drawing once more and count what is on it rather than what it costs. The fib(30) tree has 2,692,537 nodes and 31 labels, which means every node on it is one of thirty-one things. Now make the move the picture has been asking for: glue every node carrying the same label into a single node. All 514,229 copies of fib(2) become one circle. What comes out is not a tree any more, because a tree's node has one parent and fib(28) now has two — fib(30) and fib(29) both point at it. It is a graph, and it is small.

The tree is 2,692,537 calls.
The graph is 31 circles and 58 arrows — every circle except fib(0) and fib(1) points at two others (29 × 2).

Then run the same procedure with a notebook open beside it — look the label up before working anything out, write the answer down after. Each of the 31 circles gets worked out once and each of the 58 arrows gets followed once, so the whole run is 59 calls (1 root + 58 arrows). Not one line got faster. Nothing was rearranged, nothing was skipped, no branch was proved empty. 45,600 times fewer calls (2,692,537 ÷ 59), and the entire saving is the gluing. Say it in the general form, because this is all that dynamic programming ever is: an exponential tree collapsed into a polynomial graph, and the collapse factor is the speedup. fib(90)'s tree held 9.3 quintillion calls and 295 years of machine time. Its graph holds 91 circles and 178 arrows, and the run is 179 calls.

The notebook has a name, and the name tells you what your code has secretly been all along. Looking a label up, and only walking down an arrow when the lookup misses, is depth-first search of that graph — the notebook is precisely the thing that stops you walking the same arrow twice. That is memoisation, and it is the top-down form. The bottom-up form is where the real gift is hiding. Turn every arrow around. Suppose the circles can be laid out in a line so that every arrow points backwards. Then walking that line left to right means each circle's inputs are already finished by the time you arrive. No recursion, no lookups, one pass. That layout is called reverse topological order, and here is what it buys you: you never design a DP's loop bounds. You read them off the arrows. fib's arrows run from fib(k) back to fib(k−1) and fib(k−2). Reversed, they give 0, 1, 2, up to n. That is for i in range(2, n+1), the loop everyone writes, and it was never a convention. It is the only order the arrows permit. Edit distance's cell (i,j) has arrows to (i−1,j), (i,j−1) and (i−1,j−1). So any order that finishes row i−1 before row i is legal. Row by row works, column by column works, and diagonal by diagonal works too. That last one is why the DP parallelises: no cell on an anti-diagonal has an arrow to any other cell on it. And the bill reads off the same picture with nothing else on it: every circle worked out once, every arrow followed once, so the runtime is circles plus arrows.

You have operated this machine by hand, probably this week. A spreadsheet is a dependency graph of cells and nothing else. Typing =B4+C4 into D4 does not store a sum; it draws two arrows into D4. Press enter and the application topologically sorts the sheet, evaluates in dependency order, and caches every result in the cell it belongs to. That is why editing B4 recalculates D4 and whatever sits downstream of D4. It leaves the other nine thousand cells alone. That is bottom-up dynamic programming with a user interface on it: the graph, the order and the table, all three, and a recalculate button for the cache. The spreadsheet will even show you a legality check firing. Make a cell refer to itself, directly or round a loop of five, and it does not hang and it does not guess — it says circular reference and refuses. A graph with a cycle has no topological order, so it has no evaluation order and no bottom-up form at all. Keep that refusal in view, because it is the easy one to catch. The back half of this section is about a second, much quieter way the same permission gets refused, on a graph with no cycle anywhere in it.

Before writing a line of a DP you can price it, and the whole calculation is two numbers multiplied: how many distinct subproblems are there, and how many choices does each one examine? Ten seconds, off the problem statement, no code. Edit distance between two 1,000-character strings is the fewest insertions, deletions and substitutions that turn one into the other. It has one subproblem per pair of prefixes, so a million of them (1,001 × 1,001). And each cell examines three choices. Three million steps, about three milliseconds. The same recursion with the notebook taken away has a tree with more than 10⁶⁰⁰ leaves (C(2000,1000) paths). But the two numbers do more than price it, and this is why it is worth writing them down separately: they name which factor to attack, and there are only two. Take page 1's twenty delivery depots, priced there at 2.4 quintillion routes (20!) and 77 years. Ask it as a DP and a subproblem is which depots have I already visited, and where am I standing now. That is 2²⁰ subsets times 20 standing positions, about 21 million subproblems, each examining 20 next-steps. 419 million steps: four tenths of a second. Seventy-seven years to under half a second, and read carefully what actually happened, because it is not what people say happens. The count moved from 20! to 2²⁰. A table did not turn an exponential problem into a polynomial one. It gave the exponential a much smaller base.

Which is where the bill comes in, because a table buys time with memory, and the memory can be unaffordable. Stay with those depots and add one at a time. At 20 the table holds 21 million entries — 168 MB, and it fits. At 25 it holds 839 million — 6.7 GB. At 30 it is 258 GB (2³⁰ × 30 × 8 bytes). The clock was never what stopped you: the wall is memory and it arrives first. Now the version that catches people on a problem that looks entirely safe. Knapsack takes n items and a capacity C, and asks the best total value that fits. It has a table of n × C cells, so 100 items against a $10,000 budget is a million cells and nothing to discuss. Now write the identical budget in cents. C becomes 1,000,000, the table becomes 100 million cells and 800 MB, and not one thing about the problem changed. The input grew by two characters. There is the tell, and it is the sentence to carry away. The table is polynomial in the VALUE of that number, not in the number of bits it takes to write it. And value is exponential in bits. That is page 1's "linear" primality test wearing a new costume. $10,000 is a 14-bit number (2¹⁴ = 16,384) and 1,000,000 is a 20-bit one (2²⁰ = 1,048,576). So six more bits of input bought a hundred times the table. And a 64-bit capacity would ask for 2⁶⁴ columns — eighteen quintillion of them. So the real condition for tabling is not are there repeats. It is is the distinct-subproblem count polynomial in the SIZE of the input — the bits, never the values.

Everything up to here assumed you are allowed to build the table. Here is the condition, and it is the piece almost nobody is handed as a usable test. Its name is optimal substructure, and the standard statement — an optimal solution contains optimal solutions to its subproblems — is true and useless, because it never tells you when it is false. So here is when it is false, in one sentence: it dies the moment two subproblems compete for a shared resource. One graph, two questions, and watch one pass and the other fail. Ask for the shortest route from A to Z, and pick any stop M on the best route. The A-to-M half has to be the shortest A-to-M there is, because if something shorter existed you could swap it in and the whole route would get shorter. The swap is always legal. Now ask, on the identical graph, for the longest route from A to Z that never repeats a stop. Pick M again, take the longest A-to-M and the longest M-to-Z, glue them — and the result may pass through the same stop twice, which is not a route at all. The swap is not legal, and the reason is one word. The two halves were bidding for the same stops. In the shortest-route question there is nothing to bid for; a stop spent on the left costs the right half exactly nothing. In the longest-route question the supply of unused stops is shared, finite and contested, so an improvement to one half can bankrupt the other.

The reason to hold the test in that form rather than the textbook's is that it predicts, in advance, which problems will refuse a table. Rod cutting: a rod of length n, a price for each length, cut it for maximum value. The best cutting of the left piece and the best cutting of the right piece cannot interfere, so the table is legal and one index is enough. Now add four words to the problem — at most three cuts — and the one-index table is dead. The two pieces are now bidding for the same three cuts, and nothing in the code changed. Same story for a trading plan whose two halves of the year draw on the same fifty commission-free trades, and for two halves of a schedule that both want the one machine at 09:00. And the repair is always the same repair: put the contested resource into the subproblem's label. The subproblem stops being this rod and becomes this rod, with k cuts left; the halves stop competing because the label now states what each half is allowed to spend. That is precisely what knapsack's second index has been all along — remaining capacity is the contested resource, promoted into the label. And precisely what the depot DP's subset is. There the contested thing is which depots are still unvisited, a set rather than a number. Which explains the last two paragraphs in one line: the table's size is the state space of the contested resource. A capacity is one number, so the table is C columns wide and merely pseudo-polynomial. A set of 30 depots is 2³⁰ states, so the table is 258 GB. And which vertices have I used on a general graph is that same 2ⁿ, which is exactly why longest-simple-path has no cheap DP and is not about to get one.

So every recursion you meet sorts into four boxes, on two axes that are usually taught as one:

Nothing repeats, halves independent — divide and conquer, the last section. A table has a 100% miss rate and buys nothing.
Repeats, halves independent — build the table. The only box where it is both legal and worth it.
Repeats, halves compete — no table is legal. Get the resource into the label, or do not table it.
Nothing repeats, halves compete — search, and the only thing that makes search affordable is a bound you can prove before you walk a branch. Nothing on this page buys you that; it is a page of its own.

And the asymmetry between the two failures is worth more than the grid. A table on a non-repeating problem costs you memory. A table on a competing problem costs you the answer. The first is waste you can measure in an afternoon. The second is code that runs, returns a confident number, and agrees with brute force on your four-vertex test graph. Because a graph that small is exactly the one where the two halves have nothing to collide over.

One last thing to do before writing the table, and it takes ten seconds and saves an afternoon: design the subproblem space as small as you can, then check that it is CLOSED. Closed means it already contains everything your own recursion produces. Watch it earn its keep. Twenty matrices to multiply in a row, and you want the cheapest bracketing — the multiplication order is entirely yours to choose and the sizes make the difference enormous. Guess the last multiplication: it splits the chain somewhere into A1…Ak and Ak+1…A20. The left half is a prefix, so a table indexed by prefix length has a cell for it. The right half is not a prefix — fine, allow suffixes as well. Now recurse into that right half, A6…A20, and split it at 12. Out comes A6…A12, which is neither a prefix nor a suffix of the original chain. Your own recursion just emitted a subproblem your table has no cell for. The smallest set closed under that step is every contiguous run, and for twenty matrices there are 210 of them (C(21,2)). So the table takes two indices. The second index was forced by the recursion, not chosen by taste. That is the honest answer when someone asks how many dimensions a DP needs. Price it while it is in front of you: 210 subproblems, up to nineteen splits each, 1,330 evaluations in total (C(21,3)). That is against 1,767,263,190 distinct bracketings (Catalan(19)). Run the same check on fib and it passes immediately — k emits k−1 and k−2, both already in the set of single integers, so one index is enough. Which is why fib is the example everybody opens with, and also why it teaches you nothing whatsoever about dimensionality.

Three rules to close, one working sentence each. Cut-and-paste is the only proof a DP ever needs. Assume the optimal whole. Cut out the piece that solves one subproblem, and paste in a better piece for it. If the result is still valid and it is better, you have contradicted optimal. So that piece was optimal, and the table is licensed. And the failure of that proof is the shared-resource test firing. Sometimes the pasted-in piece comes back invalid rather than merely no better — the route visits a stop twice, the plan spends a fourth cut. That is not a proof you were too slow to find. It is the structure telling you the halves compete, and no table is legal until the contested thing is in the label. Second: bottom-up wins on constants, memoised wins on sparsity, so choose by asking what fraction of the table ever gets touched. Bottom-up fills every cell, makes no calls and walks memory in order, which is worth two or three times per cell. Memoised only ever reaches cells the problem actually needs. So on a knapsack whose item weights are all multiples of 1,000 it touches one column in a thousand, and wins by far more than three. Third: store the CHOICE beside the value. A value table on its own makes reconstruction cost more than constant time per step. With the split index saved, printing the bracketing for 100 matrices is 99 lookups. Without it, each of those 99 steps has to re-scan up to 99 splits to work out which one produced the number it is standing on, so 9,801 (99 × 99). One extra integer per cell. And now notice what every table in this section did to earn its answer. It examined every choice at every subproblem — three per cell in edit distance, nineteen per cell in the matrix chain. Then it let the arithmetic work out which one was right. The next move refuses to examine them at all. It picks one, commits, never looks back, and pays the whole cost of that refusal in proof.

05Choose first, and pay for it in proof

One test runner. A day of job requests queued against it, each naming a start time and an end time that will not move. A 90-minute integration suite at 09:00, a 20-minute lint at 10:20, an 85-minute build at 10:35. And the machine runs one job at a time. Run as many of the thousand requests as you can. The table from the last section will answer this, and it will do something faintly absurd on the way. Before it can name the first job of the day, it works out the best schedule for every possible remainder of the day. So invert the two steps, because that inversion is all of it.

Dynamic programming, at each subproblem: examine every choice, solve the subproblems each choice produces, then let the arithmetic say which choice was right.
Greedy, at each subproblem: make the choice first, by a rule, then solve the one subproblem that choice produces.

Solve, then choose. Choose, then solve. Everything anyone memorises about greedy falls out of those two lines and none of it needs remembering separately. One choice per step means one subproblem per step, so the calls form a chain and not a tree — a thousand jobs, a thousand calls, and no label ever appears twice. Nothing repeats, so there is nothing for a table to share, and sharing was the table's entire job. No table, therefore no memory. Top-down, because the choice gets made before any answer exists to check it against. And the practical half, which is the reason to hold the inversion rather than the bullet points. A greedy algorithm lives inside a DP you have already written. It is what remains when one choice at each subproblem can be shown to be safe. That word is the price. Committing to a choice you never revisit means every branch you did not walk has to be argued away rather than examined — and the argument is two lines long. We will write them.

So write the honest table first and do not jump to the answer, because the collapse is the lesson and you only get to watch it if you build the thing that collapses. Design the subproblem the way the last section forced you to: pick a job, ask what your own recursion emits, keep going until the set is closed. Pick a job in the middle of the day and it cuts the day in two — what fits before it, what fits after it. The piece on its left is not a prefix of anything. It is a bounded window: the machine is free from time a until time b, how many jobs fit strictly inside? Windows have two ends, the ends are job endpoints, and a thousand requests give 501,501 subproblems (C(1002,2)), each scanning up to a thousand candidate middles — call it 167 million evaluations (C(1002,3)). That table is correct, and by now you could write it in your sleep. Now assume the one thing this section owes you a proof of, and watch what it does to the geometry: the job that finishes earliest is always safe to run. Ask where that job sits. It sits at the far left — by definition nothing finishes before it — so the piece it leaves behind has no left end at all. The machine is free from time f onward, and that is the whole description. That subproblem's own earliest-finishing job sits at its left end, and so on down. The recursion never emits a two-ended window again.

Two-ended windows: 501,501 subproblems, 167 million evaluations.
One-ended windows: 1,000 subproblems, one look each.

A one-ended window is just a time, so there are only a thousand of them, and each has exactly one choice worth examining — which leaves nothing to store. Sort the requests by finish time (≈9,966 comparisons) and walk left to right, taking any job that starts after the last one you took has ended. A thousand steps and no table. Read carefully what removed the table. It was not a cleverer table, and it was not a tighter loop. The subproblem space fell from a triangle to a line, and it fell because a safe choice sits at an end. That is the collapse to hunt for every time. A choice in the middle leaves two pieces and you have a DP; a choice at an edge leaves one and you have a scan.

Which leaves the one genuinely creative decision in the method — which job — and the instinct nearly everybody brings to it is backwards. Choose the key by what the choice leaves behind, not by what the choice costs. Two rules a careful person writes first, and both are wrong. Earliest start: drop a request for 08:55–17:00 into the queue alongside eight ordinary one-hour jobs, and earliest-start takes the long one — 1 job where 8 were sitting there. Easy to see, easy to reject. Shortest first is the seductive one, because the thing being counted is jobs and a short job looks like the cheapest way to buy one. It is the three requests at the top of this section. The lint is the shortest thing in that block at twenty minutes, and running it blocks the suite ending 10:30 and the build starting 10:35, so the block yields 1 job instead of 2. Stack a hundred such blocks across a week, three hundred requests in all: shortest-first schedules 100 and earliest-finish schedules 200. Half, and it stays half however many blocks you add — a property of the rule, not an unlucky day. And look hard at what that lint did, because the last two paragraphs of this section are about the same thing wearing other clothes: it billed twenty minutes and consumed a hundred and eighty. Nothing else in the day can run between 09:00 and 12:00. Earliest finish is the only one of the three that asks a question about the residue instead of about the job. Not which job is cheapest, but which job hands the machine back soonest. And a machine free from 10:30 runs everything a machine free from 10:40 runs, and possibly more. Then the detail that stops you hunting for the one true key. Run the day backwards, latest start first, and you get a completely different schedule of exactly the same size — equally optimal, for the mirror-image reason. The key is not unique because the freedom is not one-sided. You were never looking for the best job. You were looking for the job that damages the rest of the problem least, and a day has two ends to be undamaged from.

Now the licence, and notice first what you are not going to prove. My rule produces the optimal schedule is a claim about every possible input and all thousand choices the rule makes on it. There is no handle anywhere on that sentence. That is why people write greedy algorithms, test them against the inputs they happened to think of, and ship. Swap it for a claim that has a handle. Take an optimal schedule — not yours, somebody else's, the best one that exists, and you are told nothing whatever about what is in it. Call its first job o. Call your first pick f, the job that finishes earliest in the whole day. By construction f finishes no later than o. So delete o from their schedule and drop f into the hole: every remaining job in their schedule started after o finished, so it starts after f finishes too. Still legal, still exactly the same number of jobs. An optimal schedule containing your choice exists. That is the argument, both lines of it, and read what it did to the claim. You never showed your answer was optimal. You showed that some optimal answer agrees with your first move. Then you aim the identical two lines at what is left of the day. The agreement extends one job at a time, until their schedule is yours. It is the sibling of the cut-and-paste proof from the last section, and the difference is a single word. Cut-and-paste pastes in something better and forces a contradiction. The exchange argument pastes in something equal and forces coexistence. Both of them edit a stranger's optimum, and neither ever constructs one. This is also the third of this page's four moves being spent — skip it, paid for in proof. The exchange rate is lying on the table: two lines of argument, and 167 million evaluations that never happen. Not pruned by a bound, not cut short by a test at runtime. Argued away before the program starts. One honest rider: the proof delivers an optimum, never the optimum, which is precisely why the backwards scan's completely different schedule is just as correct.

So when do those two lines refuse to go through? Two ways, and this section owes you both — the key can be right and the choice can still strand a resource nothing else fits into, or the key can simply be counting the wrong thing. The first shows up cleanest on the problem you already have a table for. A 10 kg case and three things to pack: A weighs 6 kg and is worth $60, B and C weigh 5 kg each and are worth $45 each. The greedy key is not in doubt here — value per kilo, the density — and it ranks them correctly, A at $10/kg against $9/kg for the other two. If the goods can be cut, and plenty can — sand, fuel, bandwidth, an advertising budget, a bond allocation — that rule is exactly optimal. And the exchange is almost too easy. Any packing that leaves out a kilo of the densest thing still available can swap that kilo in for free. Now make the goods indivisible and change nothing else. Same items, same key, same code.

Cutting allowed: $96 (all of A, 4 kg of B).
Best whole items: $90 (B and C, exactly 10 kg).
The density rule on whole items: $60 — A, and four kilos of air.

Be precise about why, because it is not bad luck. A advertised $10 a kilo, and that figure was worked out over the 6 kg it consumes. It also stranded 4 kg that nothing left in the pile can fill. Charge the air to the item that created it, and A's true density is $6/kg ($60 ÷ 10 kg) against B-and-C's $9/kg ($90 ÷ 10 kg). So the key you sorted on was wrong by exactly the space the choice wasted. And you cannot know that amount without looking at the rest of the pile, which is the one thing this entire method refuses to do. The exchange refuses in your hands, in a line. Take the optimum {B, C} and try to edit A into it: A weighs 6, so evicting one of them still leaves you at 11 kg, and you have to throw out both. $90 out, $60 in — the swap is not free, so no optimal packing need contain your choice, and the licence is denied before you have written any code. Which gives the property in one sentence: greedy is optimal exactly when leftover capacity is always fillable. Hold that as a working test rather than a theorem — for some problems the exact condition is harder than it looks, and the next paragraph is one of them. Divisible goods can always fill a residue at the next-best density, so nothing is ever stranded and the swap is always free. Indivisible goods can leave a residue that nothing fits into, and the stranded space dilutes the very density you optimised for.

The same test decides a problem that looks nothing like a rucksack, and you can run it in your head. Pay with coins {1, 3, 4}: to make 6, the greedy takes the 4, is left with 2, and pays that as 1+1 — three coins, where 3+3 is two. Taking the 4 leaves a residue of 2 that nothing covers efficiently, which is the stranded four kilos in different clothes. With {1, 5, 10, 25} the greedy is optimal for every amount there is, because every residue those coins leave can be covered cleanly — and here is the rider I promised. For coin systems the exact condition is genuinely fiddly: it is settled by testing all amounts up to a computable bound, not by inspection. The diagnostic is what transfers, and it is worth carrying into every packing, scheduling and budget problem you meet. Before writing a greedy rule, ask whether any single choice can strand a resource it does not itself consume. If nothing can be stranded, the exchange will go through and you can go and write the scan. If something can, the exchange will cost you, and you knew that before writing a line. That is the first refusal. The second is blunter, and stranding has nothing to do with it: the key can simply be counting the wrong thing. Put a value on those jobs — a nightly build worth $500 to get finished, a lint worth $50 — and earliest-finish dies on the spot. Take one job running 09:00–17:00 for $500 and two short ones at $50 apiece. The scan takes both short ones for $100, where the long job alone was worth $500. The exchange says so in one move, because swapping a $50 job into that optimum evicts $500. Nothing was stranded there. The rule was counting jobs, and jobs were never what you were being paid for. The rule is dead. The table is not — it never trusted a rule — and that is the real reason this section made you write the DP before the scan. The DP is not scaffolding you throw away once the greedy works; it is what you fall back to on the day the licence is refused. Every move on this page so far has removed work outright: reshape the tree, share the answers, argue the branches away. The last one removes nothing at all. It leaves every step exactly where it is and changes only when the steps happen. That turns out to be enough to make the most expensive operation in a data structure free on average — and to make that a worst-case guarantee rather than a hope.

06Don't do the work yet

Append a million items to a list, one at a time, and time every append.

One of those appends moves 524,288 items into a fresh block of memory.
All 1,048,576 appends together move 2,097,151.

Just under two moves per append across the whole run, and one append in the middle of it did half a million on its own — 262,144 times the average. Both numbers are true of the same million appends, and holding them at once is the entire idea. It is also where the idea gets the wrong name. "Free on average" makes everybody reach for average-case, and there is no probability anywhere in this. Average-case, as page 1 had it, is a claim about a distribution of inputs — a hope about what typical data does to you. Amortised quantifies over sequences instead, and assumes nothing whatever about their contents: it is a worst-case claim wearing a per-operation costume. Every sequence of a million appends costs at most about two million moves — the sequence you wrote, the sequence a fuzzer stumbled into, the sequence someone chose after studying your growth rule specifically to hurt you. Which makes the promise you may now make unusually precise, and it points two ways at once. You may promise throughput: a million appends, bounded, on every input there is. You may not promise latency: that half-million-move append is real, it is the spike sitting in your p99, and the amortised bound never once denied it. And this is not a demonstration structure. It is the list you have appended to in every language you have ever used, and the rule that produces both of those numbers is what the next four paragraphs take apart.

Start with the cheapest form of the argument, which needs no accounting at all — only a quantity that cannot be created twice. An editor's undo stack takes pushes, takes pops, and takes one more operation: revert to the last save, which pops everything back to the mark. A single revert can pop 999 entries in a thousand-operation session, so the obvious bound multiplies the worst operation by the number of operations and reports 999,000. Now say the sentence that destroys it. Nothing can be popped that was not pushed. A thousand operations contain at most a thousand pushes. So at most a thousand entries ever exist to be removed. And every pop in the session — one at a time, or 999 in a burst — comes out of that same allowance of a thousand. The whole session costs at most 2,000 units, a thousand pushes and a thousand pops, and no series was summed to get there. Look at what the naive bound actually assumed: that every operation could be maximal simultaneously. It cannot, and the structure itself is what forbids it — the expensive revert is expensive precisely because it empties the stack, which is the same act that makes the next revert free. The worst case of one operation and the worst case of a sequence are different questions, and multiplying the first by n answers neither. So the move, whenever you meet a structure with one operation that occasionally explodes: find the quantity the cheap operations create and the expensive operations consume. Bound how much of it can exist, and the expensive operations are bounded for you, with no arithmetic at all. You are not adding costs up. You are pointing at something that cannot be spent twice.

The growing array has no such obvious currency, so invent one and charge for it. Prepay: make every cheap operation pay more than it costs, park the surplus on the object, and spend it when the expensive operation finally arrives. Charge 3 for an append — one unit writes the new item, two units stay behind as credit sitting on that item. Now watch a copy get funded. The array is full at capacity c, and the next append must move all c items. The items appended since the last copy number exactly c/2, because the last copy is what left the array half full. Each of those carries 2 credits. c/2 items × 2 credits = c, and the copy costs c. Not comfortably enough. Exactly enough, every time, at every size. Put the million on it: at 1,048,576 items the 524,288 appended since the last copy hold 1,048,576 credits between them, and the copy about to happen moves 1,048,576 items. And that 3 was not tuned until the algebra worked. You derive it by asking who funds a copy. Half the array does, since the other half was already there when the last copy ended. So each of them must carry 2, and 2 plus the item's own write is 3. The condition that makes the whole scheme legal is one you can check by looking rather than by proving. Stop the program at any instant, count the credits sitting on the structure, and the pile must never be negative. A negative pile means an expensive operation happened that nothing had paid for, and your bound is fiction.

Credits parked on individual items get unmanageable the moment a structure has more than one kind of expensive event. So replace the pile with a single number read off the whole object — the potential, written Φ. Textbooks hand you the right Φ and then verify it, which teaches you nothing, because verifying a function is not inventing one. Here is the recipe, and it is two conditions.

Φ reads 0 immediately after you pay a big cost.
Φ has grown to equal the next big cost just before you owe it.

So: find the next expensive event, then find something that counts up to its price. For the array the expensive event is copying c items when it fills. Right after a copy the array is half full. Just before the next one it is completely full. So the thing that runs from nothing up to c across that stretch is how far past half full you have got. Doubling it makes the units come out right — Φ = 2·size − capacity. Check both conditions and it takes one line each. Half full means 2·size = capacity, so Φ = 0. Full means size = capacity = c, so Φ = c, which is the copy cost precisely. The function was derived, not recalled. Now spend it, using the definition that does all the work — amortised cost = actual cost + the change in Φ — on the two appends that look least alike in the entire run.

An ordinary append: actual 1, size rises by one so Φ rises by 2. Amortised 3.
The append at item 524,289: actual 524,289 (one write, 524,288 moves), and Φ falls from 524,288 to 2. Amortised 3.

The catastrophic append and the trivial one cost the same, and that is not a coincidence worth admiring. It is what the two conditions were chosen to produce — Φ was built to be a reservoir that fills at the rate the disaster grows and empties exactly when the disaster is paid.

Adding ΔΦ looks like a licence to write down whatever you want, so here is why it is not, and it is the one piece of algebra in this section. Sum the amortised charges over a whole sequence. Each step contributes its actual cost plus Φ_after − Φ_before, and every intermediate Φ therefore appears twice with opposite signs and cancels. What survives the sum is the actual total plus Φ at the end minus Φ at the start — two terms, no matter how many operations ran. Choose a Φ that starts at zero and never goes negative and the amortised total is a genuine ceiling on the actual total, for the whole sequence, with the intermediate detail annihilated. Check it against the run we have been counting. The charges sum to 3,145,727 — three per append, except the very first, which only needed two. The actual work was 2,097,151 moves. The difference is 1,048,576, which is exactly Φ at the end: credit still sitting on the array because the copy it was saving for never happened. The slack in an amortised bound is not slop — it is a quantity you can point at. Then run the same device backwards and it proves lower bounds, which is the half almost nobody is shown. If no single step can change Φ by more than some amount, a run that must move Φ a long way needs many steps. Take page 1's inversion count as the potential. One swap of neighbouring items changes it by exactly 1. A thousand items in reverse order carry 499,500 inversions (1000 × 999 ÷ 2) and a sorted list carries none — so any method restricted to swapping neighbours needs at least 499,500 swaps. That is not a remark about bubble sort being slow. It is a floor under every algorithm of that shape, including ones nobody has written, and it took one line of counting.

Now the failure mode that turns all of this from analysis into something you will use on Monday. The resize rule everyone writes first is the symmetric one: double when full, halve when half empty. Tidy, and catastrophic. Fill an array to 1,000 items at capacity 1,000. Append: full, so copy 1,000 items, capacity becomes 2,000. Delete: size is back to 1,000, which is half of 2,000, so copy 1,000 items and capacity returns to 1,000. You are exactly where you began, and you may now do it again forever. Every single operation copies a thousand items — a thousand operations for 1,000,000 moves, where the correct policy costs about 2,000. And notice who wrote that adversarial input: a loop that appends one item and pops one item. A work queue at steady state. Nobody had to be malicious; the pathological case is the ordinary case, parked on the boundary. The repair is one number. Grow when full, shrink at a quarter, never at a half. Then every resize leaves the array exactly half full. Growing takes size c to capacity 2c, and shrinking at size c/4 takes capacity to c/2. So from the instant a resize ends, you must add half a capacity or remove a quarter of one before you can trigger another. Those cheap operations fund it. The gap between the trigger and its reverse has a name worth carrying: a deadband. Any threshold that fires expensive work needs one, or some state sits adjacent to both triggers and oscillates. You will meet the identical arithmetic in three more places. A cache evicts down to a low-water mark instead of stopping the moment it is under the limit. An autoscaler scales out at 70% and in at 30% rather than both at 50%. And a circuit breaker opens on failure, then refuses to close until a quiet period has passed. Same rule, same reason, and the same ordinary traffic finds the flaw when it is missing.

Which leaves the move this whole section was built for, and it is the one that sounds like negligence. Do not repair the structure at the moment you damage it. Let it rot. Every cheap edit deposits potential, and you repair during a rebuild those cheap edits have already paid for. A store of a million records, and half a million of them to delete. Delete in place and each deletion closes its own hole — around 500,000 records shifted each time, so 250 billion moves in total (5×10⁵ × 5×10⁵). Instead, write a tombstone and walk away: one mark, constant time, the corpse stays where it is. Dead records pile up, Φ is how many of them there are, and when the dead reach half the store you rewrite the 500,000 live records once and Φ drops to zero. Half a million tombstones plus one rewrite of half a million is 1,000,000 units — two per deletion, worst case, against 250 billion. It is the post you never file. Filing each letter as it lands costs a walk to the cabinet per letter, and letting the pile grow costs nothing. The single sort is fired by the pile itself, once the dead half of it has taken over the desk. It costs less than all the walks you skipped. Two things to take with you, and the first is the reason Φ is worth more than the array it was introduced on. Φ is a modelling choice, not a formula — it can measure anything that counts up to a price, including your disagreement with a rival. Set Φ to the number of pages your cache holds that a clairvoyant's cache does not, and "how much worse can I be than something that sees the entire future?" turns into counting. Cut the stream into stretches that touch 64 distinct pages. LRU misses at most once per distinct page in a stretch, so at most 64 times. And a stretch's 64 pages plus the page that opens the next stretch are 65 distinct pages, which no 64-page cache can hold — so even the clairvoyant misses at least once per stretch. Sixty-four against one, stretch after stretch, and no deterministic policy beats that factor. Give LRU 64 pages against a clairvoyant holding 32 and the factor collapses to 1.94 (64 ÷ 33) — which is why a little extra cache buys far more than its size suggests. The second is a warning. None of this is in the code. There is no credit field, no potential variable, nothing counting; 2·size − capacity is computable from two numbers the array already stores and not one line ever reads it. The accounting exists so that a person can make a promise about a machine, and a credit counter written into the structure spends real memory and real time on a fiction whose only virtue was being free. So the fourth move is spent. The currency this page named for it at the top turns out to be exact: postpone it, paid for in patience — the patience to run a structure that is temporarily, deliberately wrong.

Four moves, and there were never five.

Rearrange it — the tree changes shape.
Share it — the repeats collapse.
Skip it — the branches are argued away.
Postpone it — the same work lands where it is cheap.

Not one of them made a single line faster. That was never the thing on offer.