The cost is the number of subproblems

Here is the whole of the edit-distance recurrence. The distance between a prefix of length $i$ and a prefix of length $j$ is zero when both are empty, is $i$ or $j$ when one of them is, and otherwise is one more than the cheapest of three smaller problems — substitute, delete, insert.

Written down literally, that is nine lines of code, it is correct, and on the words kitten and sitting it makes 29,737 calls.

The same nine lines with a table beside them, so that an answer already found is looked up rather than recomputed, make 56.

Nothing about the arithmetic changed. No operation was made cheaper, no loop was tightened, no comparison was avoided. What changed is a fact about the shape of the problem — that the recursion reaches the same subproblem along many different routes — and that fact was true of the first version too. It was simply not being used.

The two numbers a table has, and the counter that reports them #

Every counter on this site so far charges for something done to the data: a comparison of two elements, a character examined inside a string comparison, a block moved between memory and disk, a bit emitted by a coder, a bit of state retained while a stream goes past. Each of those is a count of acts performed on an input, and each is exact.

A dynamic program does not have that shape. Its work is settled before any data is touched, by two quantities that belong to the recurrence rather than to the input:

• how many distinct subproblems there are, and
• how many transitions each one considers — one per argument of the minimum.

Their product is the work. The literature’s $\Theta(nm)$ multiplies them and reports only the answer, which is exactly the move the constant is the content exists to object to: the edit-distance table and the longest-common-subsequence table over the same two strings have identical cell counts and different transition counts, and no bound written in that form can tell them apart.

So this field’s counter reports both, and two more beside them. cells is subproblems given a value. evals is transitions considered. probes and hits are lookups and lookups that found something, which is the whole difference between a recursion and a memoised recursion and is invisible in cells. And peakLive is how many cells are held at once, which is a different resource from how many are computed — three of the methods in this field compute strictly more in order to keep strictly less, and a counter without that field could not describe any of them.

That is the site’s ninth counter, and the case for it being new rather than a rename is the same case the streaming field made for the eighth. The space counter measures scratch taken beside an input: measuring what an algorithm keeps charges merge sort for a buffer of $n$ slots on top of an array of $n$ that was already there, and the interesting quantity is the ratio. Here the table is not overhead beside the data — it is the computation, its size is decided by the recurrence and not by the input’s length, and expressing it as a fraction of the input would report a number that grows without limit and means nothing.

Why the routes multiply #

The circles in the first plate are worth reading rather than glancing at, because the exponential is entirely visible in them and it is not the exponential most accounts describe.

The usual explanation is that the recursion tree has depth $n + m$ and branching factor 3, so it has $3^{n+m}$ nodes. That is an upper bound and it is loose by an enormous factor: the tree cannot branch three ways once a prefix is exhausted, and the three children overlap heavily.

The exact count is the number of monotone lattice paths from $(n, m)$ to each cell, summed — the Delannoy numbers, which grow like $(3 + 2\sqrt2)^{\,n}$, or about $5.83$ per character added. Measured, the growth from four characters to twelve is a factor of 785,000 in calls against a factor of 6.8 in subproblems.

The right-hand column is the thing being wasted, and it has a name: overlap. A recurrence whose subproblems overlap is one where the ratio in that column grows; a recurrence whose subproblems do not overlap gets a ratio of exactly one, and memoising it buys nothing at all. Binary search is the standard example — each call splits into a single subproblem, no subproblem is ever reached twice, and a memo table attached to it would record $n$ entries and answer no question from any of them.

The rectangle #

Once the answers are written down, the picture of the computation stops being a tree and becomes a table: one cell per pair of prefix lengths, filled in some order, each cell reading three neighbours.

Two things about that grid are worth stating precisely, because both get elided.

The table is the output, not the workspace. Cell $(i, j)$ holds the edit distance between the first $i$ characters of one string and the first $j$ of the other. Every one of those is a real answer to a real question, and several of the algorithms later in this field exist because some of them can be thrown away and others cannot.

The order is not implied by the recurrence. The recurrence says what a cell depends on; it does not say when to compute it. Row by row works, column by column works, diagonal by diagonal works, and top-down from the corner works. Filling the rows from the bottom upwards does not, and that failure is the subject of the next essay — it is also the reason DpTable in this site’s library throws when a cell is read before it is written rather than returning the zero an array would.

What is actually being counted, and against what #

cells is exactly $(n+1)(m+1)$ here, and that is worth checking rather than assuming, because it is the claim every bound in this field rests on. Measured on two strings of 256 characters: 66,049 cells, which is $257^2$.

evals is 197,120 on the same run — three per interior cell, one per boundary cell, none for the corner. The ratio of the two is 2.98 and it is the number a caption needs when it says how expensive a cell is. For the longest-common-subsequence table over the same pair the cell count is identical and the transition count is not, because a cell whose two characters match has one predecessor rather than three.

The two axes, kept apart from the start #

The last field on this site to arrive introduced a counter and an error to trade it against. This one introduces a counter and a second counter, and the reason to separate them on the first page rather than the fourth is that every interesting method here moves one and not the other.

The site has made this move before and it is worth naming, because it is the third field in a row where the interesting result was a second quantity rather than a better number on the first. Two counts, two rankings began it with comparisons against cache misses; space is the other axis continued it with what an algorithm keeps; and the streaming field ended by trading bits of state against the size of an error. Here the pair is cells computed against cells retained, and the methods that trade them are the whole of the field.

Three transitions, and what happens when there are more #

The edit-distance recurrence has three predecessors per cell. That number is a property of the problem and it is the second half of the cost.

A recurrence with more of them costs more per cell and does not need a bigger table. The knapsack in this field’s last essay has two transitions per cell and a table whose width is a capacity; a matrix-chain ordering has $\Theta(n)$ transitions per cell and $\Theta(n^2)$ cells, which is where the cubic in its bound comes from and it is not visible in the table at all. Reading $\Theta(n^3)$ as “the table is a cube” gets the shape of that computation wrong in a way that matters the moment somebody tries to make it fit in memory.

Where the two numbers come apart in practice #

It is worth naming the three shapes this field meets, because they are what the rest of the essays are about and each is a different answer to the question of which number matters.

A table whose cells are cheap and numerous. Edit distance: three transitions a cell, a rectangle of cells, and the whole cost is the rectangle. The interesting attacks are on the number of cells.

A table whose cells are expensive. A matrix-chain ordering has a linear number of transitions per cell over a quadratic number of cells, so the transitions dominate and shrinking the table would not help. The interesting attack is on the transition count.

A table whose cells are numerous and mostly unreachable. A knapsack indexed by capacity has a rectangle most of which no sequence of choices can arrive at. The interesting attack is on which cells are computed at all, and it is available only to a strategy that does not decide the order in advance.

Nothing in a $\Theta$ tells these apart, which is the practical reason for counting cells and evals separately rather than reporting their product. A phase that measured only the product would have produced the same bound for all three and the same advice for all three, and the advice would have been wrong twice.

The same graph on two more instances #

The claim is about the graph rather than about these four characters, so it is drawn twice more — once on a different pair of the same length, once on a shorter one where every node can be read.

The order is enforced rather than described #

DpTable.get on a cell that has not been written throws. DpTable.set on a cell that already holds a value throws too.

Both are deliberate and both caught real mistakes while this field was being built. The first is the device this site’s streaming library uses for one-pass access, and it exists for the same reason: the restriction that defines the model is the one easiest to violate by accident. A loop nest whose two loops run in the wrong order reads a cell that has not been computed, and against a zero-filled array that reads as a distance of zero — which is absorbed silently into a minimum, produces a plausible small integer at the far corner, and fits a perfectly smooth curve across a sweep of sizes.

The second catches a memoised recursion that is not memoised. If a cell can be written twice then the cell count is not the number of subproblems, it is something smaller than the number of computations, and every plate in this family would be quoting a number that is not the one in its caption.

Top-down or bottom-up is decided by a fraction #

The two ways of filling a table are usually presented as a matter of taste — recursion with a memo against nested loops — and the counters here make it a decision with a number behind it.

Bottom-up computes every cell. No calls, no probes, no stack; the loops walk the rectangle and every cell costs its transitions and nothing else.

Top-down computes only the cells some route from the corner actually reaches, and pays a call and a probe for each arrival, including the arrivals answered from the table. On the four-character instance above that is forty-nine calls for twenty-five cells — about two calls per cell, which is the branching factor once the repeats are absorbed.

So the two differ by a factor of roughly two in overhead per cell, and top-down wins whenever it computes fewer than about half the cells. That gives a rule:

$$\text{top-down wins when the reachable fraction} \;<\; \tfrac12$$

and the reachable fraction is a property of the recurrence that can be worked out in advance.

For edit distance it is one. Every cell $(i,j)$ is on some monotone route from the corner, so top-down computes the whole rectangle and pays the call overhead for the privilege — which is why every implementation of this recurrence anybody ships is a pair of nested loops.

For a knapsack indexed by capacity it is often far below a half. Only capacities reachable as sums of subsets of the item weights are ever asked about, and on a table of capacity 10,000 with a dozen items of awkward sizes that is a small minority of the columns. Top-down there is not a stylistic choice; it is the difference between a table that fits and one that does not.

And the fraction is measurable rather than guessed. Running the top-down version once and dividing its cell count by $(n+1)(m+1)$ answers the question directly, on the actual inputs, before anybody commits to a strategy. That is a cheaper experiment than either implementation is to write, and this collection is aware of no account of dynamic programming that suggests running it.

The rectangle is a floor for a strategy, not for the problem #

One more reading of the cell count, because it is easy to mistake for a lower bound and it is not one.

$(n+1)(m+1)$ is the number of distinct subproblems the recurrence defines. Any method that evaluates all of them does at least that much work, so it is a genuine floor — for methods that evaluate all of them. It says nothing whatever about the problem.

Everything interesting in this field is a method that gets under it by declining to evaluate some. A band computes eight cells in a hundred when the answer is small and returns the identical number. A cutoff computes even fewer. A top-down recursion on a sparse recurrence computes only what it reaches. None of those is a faster way of filling the rectangle; each is a demonstration that the rectangle was never necessary.

So the honest reading of $\Theta(nm)$ is that it is the cost of one strategy for the problem, and the strategy is the obvious one rather than the best one. That is an unusual thing for an asymptotic bound to be, and it is worth distinguishing from the floors elsewhere on this site: the comparison-sorting bound is over every algorithm that compares, and this one is over every algorithm that fills this table. The first is a statement about sorting; the second is a statement about a habit.

The distinction has a practical edge. A reader who takes $\Theta(nm)$ as the cost of edit distance concludes that two sequences of a million characters cannot be compared, and the conclusion is false — if they are similar, the band computes a sliver of the rectangle and finishes. What is true is that the rectangle cannot be filled, and the rectangle is a decision somebody made about how to organise the arithmetic.

What the unit is, and what it is not #

The unit in this field is the subproblem. It is not a comparison, it is not a machine word, and it is not a second.

That matters most where a bound is quoted. “Edit distance is $O(nm)$” is a statement about cells, and it is silent about three things this field spends the rest of its essays measuring: how many transitions a cell considers, how many cells are held at once, and whether all of the cells are needed. The answer to the last one is often no — a band as wide as the answer computes eight cells in a hundred and gets the same number — and a cost model that could not express the question could not have asked it.

There is one more property of this unit worth stating, because it is what makes the whole field measurable in the way this site requires. A cell count is exact, it is machine-independent, and it is reproducible: run the same recurrence over the same strings on any machine in any language and the count is the same integer. That is the same property comparisons have and durations do not, and it is why every number in this field is a count of subproblems rather than a measurement of anything that happened.