The cells are not the cost

The cost is the number of subproblems opened this field with a measurement and a slogan. The measurement: an edit-distance recurrence written down literally makes 29,737 calls on a six-letter word and a seven-letter word, and written down with a table beside it makes 56. The slogan: the cost of a dynamic program is the number of distinct subproblems its recurrence has, and everything else is bookkeeping.

That essay was careful enough to name its own exception in one paragraph, and the exception is this page. A cell has to be filled by considering the transitions into it, and edit distance has three. When a recurrence has a number of transitions that grows with the problem, the count of cells stops being the count of work, and the two have to be reported separately or the second is invisible.

The distinction is easy to state and easy to lose. How many subproblems there are is a question about the recurrence’s arguments — how many distinct calls it can make. What a subproblem costs is a question about the recurrence’s body — how many other subproblems it consults. They multiply, they are independent, and a table drawn on a page shows only the first.

The recurrence, and where the extra factor lives #

Two problems have this shape and they are the standard pair. Matrix-chain ordering: given a chain of matrices with stated dimensions, decide where to put the parentheses so that the total number of scalar multiplications is least. Optimal binary search tree: given a key set and how often each key is looked up, build the tree in which the expected search is cheapest.

Both have the same recurrence and it is worth writing once:

$$C(i, j) = w(i,j) + \min_{i \le k < j} \big( C(i, k) + C(k+1, j) \big)$$

The subproblems are the ranges $[i, j)$, and there are $n(n+1)/2$ of them — a triangle rather than a rectangle. So far this is the same accounting the first essay in this field did.

The minimisation is where the two part company. An edit-distance cell looks at three predecessors, always. This cell looks at every split point inside its own interval, which is $j - i$ of them, and $j - i$ runs from one to $n$. Summed over the triangle that is $\Theta(n^3)$, and the cubic is a property of the cell rather than of the table. Reading $\Theta(n^3)$ as “the table is a cube” gets the shape of the computation wrong in a way that matters the moment somebody asks whether it will fit in memory: the table is quadratic, it fits, and the time is cubic anyway.

It is worth checking that against the recursion the table replaces, because the whole method exists to replace one. Written as a plain recursion, this recurrence makes a call for every way of parenthesising a chain, which is the Catalan number — 1,430 for eight matrices and about $10^{16}$ for thirty. Memoised, the distinct calls collapse to the triangle, and the transitions are what is left. So the table did the same thing here it did in the cost is the number of subproblems: it removed an exponential. What it did not remove is the factor inside each cell, and nothing about memoisation could have.

The two numbers, side by side #

The clean way to see it is to report both counts at every size and take their ratio.

The last column is exactly $(n+2)/3$, which is the average interval length over a triangle, and it is the whole content of the extra factor. Edit distance’s version of that column is the constant 3 at every size, and that constancy is what made the first essay’s slogan true there.

So the general statement, which the first essay reached for and could not make with the machinery it had: a dynamic program costs the number of its subproblems multiplied by the transitions per subproblem, and the second factor is a constant often enough that people forget it is a factor.

There is a second reading of the same table that is worth having, because it says where the work actually sits. The cells near the diagonal are cheap and numerous; the cells near the corner are dear and few. Summing $j-i$ over the triangle, half of all the transitions are spent on the longest third of the intervals — so a computation that could stop early on long intervals would save most of the work, and a computation that could stop early on short ones would save almost none. That is the kind of observation that decides where an optimisation is worth looking for, and it comes out of the plate rather than out of the bound.

Why the table is triangular, and what that costs #

The absent half is not an optimisation. There is no subproblem $[5, 2)$, so there is nothing to skip, and a picture that filled those cells with anything at all would be drawing a computation nobody performs.

It is still worth noticing that the triangle is stored as a rectangle in every implementation, because addressing a triangle costs an integer division and addressing a rectangle costs a multiply. So a table of $n(n+1)/2$ subproblems occupies $n^2$ cells of memory, and the space this field counts — the cells given a value — is half the space the program allocates. Measuring what an algorithm keeps is the essay that insists on the difference between what is held and what is used, and this is a case where the two differ by exactly a factor of two, permanently, for a reason that is about address arithmetic rather than about the algorithm.

The fill order is also constrained differently. An edit-distance table can be filled by rows, by columns or by anti-diagonals, because its dependencies point up and to the left. An interval table’s cell $[i, j)$ depends on cells $[i, k)$ and $[k+1, j)$, which are all shorter intervals — so the only orders that work are the ones that go by increasing length. That is one degree of freedom rather than three, and it is the reason every implementation of these two problems looks the same while every implementation of an edit distance looks different.

Smaller instances are worth reading cell by cell, because the arithmetic of the last column can be checked by adding up what is drawn rather than by trusting a counter.

What none of those three plates shows is the weights, and the next one is drawn to make the point that they are not visible in the arithmetic at all — the same triangle, the same numbers in every cell, and an entirely different tree at the end of it.

What it is used for, and why the frequencies matter #

An optimal binary search tree is worth a paragraph on its own, because it is the one place in this collection where a structure is built around a distribution rather than around a worst case.

Every balanced tree on this site — the treap, the skip list, a red-black tree — guarantees a depth of about $\log_2 n$ for every key, and treats all keys alike. That is the right thing when nothing is known about which keys will be looked up. When something is known — when one key in a thousand carries half the traffic, which is what a real access pattern looks like — a tree that puts the popular key near the root beats a balanced one, and beats it by whatever the skew is worth.

The measurement makes the point. Over 128 keys with a Zipf-like frequency profile the optimal tree costs 26,599 in weighted depth; a perfectly balanced tree over the same keys costs more, and the gap widens with the skew. What the cubic buys is that number, computed exactly, and the reason people mostly do not compute it is the cubic.

The alternative in practice is a splay tree or a similar self-adjusting structure, which reaches the same weighted depth without being told the frequencies — by rearranging itself as the queries arrive, and paying an amortised cost for the rearranging. That is a different trade with a different guarantee, and the comparison between them is the same one expected is not average is about: one structure is optimal for a distribution it was given, and the other is competitive against whatever distribution turns up, and neither dominates.

There is a further reason this problem earns its place in a field about tables. Its input is not a string or an array of values; it is a probability distribution, and the recurrence’s weight term $w(i,j)$ is the total frequency of a range. That is a prefix sum, it is computed once in linear time before the table starts, and the cost of not noticing is an extra factor of $n$ on top of the cubic — a fourth power for a problem that is cubic, from a subexpression that looks harmless inside a loop.

Three ways a recurrence can be expensive #

Setting this beside the rest of the field makes the taxonomy small enough to hold, and it has exactly three entries.

The subproblems can be too many. That is the plain recursion’s failure and it is the one memoisation fixes: 29,737 calls collapsing to 56 cells. The repair is a table, and after it the count of subproblems is a count of the recurrence’s distinct arguments and nothing else.

The subproblems can be too many for the input. That is the knapsack’s failure. Its table’s width is a capacity written in the input rather than a count of things in it, so the cell count is exponential in the length of the input even though it is polynomial in the capacity’s value — the pseudo-polynomial trap, and the one place in this field where a table’s dimensions mislead in the other direction.

Or each subproblem can be expensive. That is this page. The arguments are few, the table is a triangle, and the body of the recurrence consults a number of other subproblems that grows.

Those three failures are independent and a single problem can have any combination of them. What they share is that none is visible in the sentence people use to describe a dynamic program — fill a table of subproblems — and each is visible in one of the two counts this field reports. That is the argument for reporting both, and it is why the counter here prints cells and transitions on every plate rather than a single number called cost.

The taxonomy also says where to look for an improvement, which is the practical payoff. A problem in the first category wants memoisation. A problem in the second wants its parameter examined — a rounding, an approximation, or a different subproblem set. A problem in the third wants something said about its cost function, and that something is the next rung’s subject.

Where a shape stops predicting a class #

This rung’s finding is narrow and it is worth stating narrowly, because the temptation is to conclude something larger.

Nothing here says the first essay in this field was wrong. Counting subproblems is the right first move, it is the move that turns an exponential recursion into a polynomial one, and the 29,737-to-56 measurement is exactly what it claims to be.

What is wrong is a shortcut the slogan invites: reading a table’s dimensions off the recurrence and calling that the class. Three tables with the same dimensions can have three different classes, and this field now has all three:

The middle row is a cell that has to know where it is, where three tables and seven transitions cost three times as much and stay in the same class. The third row is a different class from a table of the same order of cells. The dimensions of the table are not the class, and the only reliable way to get the class is to count both quantities and multiply, which is what this field’s counter has been reporting all along and what no figure before this one plotted separately.

What a reader should take from a bound with two factors in it #

There is a habit this rung argues against and it is worth naming, because it is the habit rather than any particular error that costs people time.

The habit is reading a complexity class as a description of a shape. $\Theta(n^2)$ is heard as a square of work, $\Theta(n^3)$ as a cube, and the picture that comes with the hearing is a picture of storage. For the recurrences most people meet first — edit distance, longest common subsequence, the knapsack — the picture is accurate, because the transitions per cell are constant and the table really is the work.

For an interval recurrence the picture is wrong in a specific and expensive way: it suggests that the computation will not fit in memory, when in fact it fits comfortably and merely takes a long time. Somebody acting on the picture reaches for a rolling frontier or a divide-and-conquer traceback, both of which address a space problem this computation does not have, and neither of which touches the factor that is actually large.

The corrective is the one this field has been building towards since its first plate. Report the cells and the transitions separately, and let the class be the product. A table’s shape then predicts its space, its transitions predict its time, and the two stop being confused because they are two numbers rather than one.

The other two interval problems this field could take #

An interval recurrence is a shape rather than a problem, and two more instances of it are worth naming because they show how far the shape reaches.

Matrix-chain ordering, which the table above measures, is a scheduling question: a chain of matrices can be multiplied in any parenthesisation, all of them give the same product, and the number of scalar multiplications differs by orders of magnitude between the best and the worst. The subproblems are contiguous stretches of the chain, the transitions are the places to split, and the whole computation is the triangle.

Optimal polygon triangulation is the same recurrence wearing a different picture: a convex polygon is cut into triangles by non-crossing diagonals, the cost is the total length of the diagonals, and the subproblems are contiguous stretches of the boundary. It is exactly the matrix-chain recurrence with different weights — the correspondence is a bijection between parenthesisations and triangulations — and that is worth knowing because it means a measurement of one is a measurement of the other.

And optimal file merging, where a set of runs must be combined pairwise and the cost of a merge is the total size of what it touches. Under the constraint that only adjacent runs may be merged, it is the interval recurrence again; without the constraint it is Huffman’s problem and collapses to $n\log n$ with a heap.

The third is the interesting one for a collection that measures rather than classifies. The same problem is cubic with an adjacency constraint and linearithmic without it, and the constraint is one clause in the problem statement rather than anything about the algorithm. That is the sharpest available demonstration that the subproblem set is decided by the question rather than by the method — remove one restriction and the triangle of subproblems is not needed at all.

What a triangular table costs to walk #

There is a practical detail this field has not measured and it belongs beside the transition count, because it can dominate at the sizes where these computations are actually run.

The triangle is stored in a rectangle, so the cells that hold values are half of the memory allocated, and — more importantly — the cells that hold values are not contiguous. Filling by increasing interval length walks the table along diagonals, and a diagonal of a row-major rectangle strides by the row width. So an interval fill’s memory access pattern is a strided sweep rather than a sequential one, at every level.

That is exactly the pattern where an algorithm looks measures for array algorithms and a list and a block of memory measures for graph traversals, and it is the pattern the cache model on this site is worst for. Nothing on this page reports a miss count, and the transition count above is therefore a count of arithmetic in a computation whose real cost at large $n$ may be elsewhere.

The repair is known and is a fourth kind of subproblem-set decision: store the triangle in diagonal-major order, so that a fill sweeps contiguously. That changes no count on this page, changes no answer, and changes the memory behaviour completely — which makes it a fifth instance of the pattern this ladder keeps finding, where the decision that matters is one the recurrence does not record.

What the counter does not distinguish #

Two things, and the second is the next rung.

There is one more consequence worth drawing out, because it changes what a reader should do with a bound rather than merely how to read one. If the class is the product of two counts, then an improvement can attack either factor, and the two kinds of improvement look nothing alike. Attacking the cell count means finding that fewer subproblems are reachable — which is what the same table, filled two ways measures when a top-down fill skips cells a bottom-up fill computes. Attacking the transition count means finding that most of the candidates inside a cell cannot win. The first is about the recurrence’s arguments and the second about its body, they compose, and a problem where both are available drops by the product of the two savings.

A transition is one unit whatever it does. A split-point evaluation here reads two cells and adds a weight; an edit-distance transition reads one cell and compares two characters. Charging both as one is a cost model, it is the site’s own, and it is the same convention one run, four counts, four answers is about — the unit has to be named before the number means anything.

And the minimisation is a scan. Every one of those $j-i$ split points is examined, in order, and the minimum is taken. Nothing in the counter says whether that scan is necessary, and this is the point at which the interesting question arrives: is it? A recurrence whose optimal split point cannot move very far when the interval grows by one would not need to look at every candidate, and if the range that has to be searched telescopes across a whole diagonal, the extra factor of $n$ disappears.

Where this ladder goes next: the argmin that cannot go backwards #

The plates above measure a cubic and take it as given. It is not given.

For the optimal binary search tree — and for a family of problems with the same property — the split point that wins for the interval $[i, j)$ lies between the split points that win for $[i, j-1)$ and $[i+1, j)$. That is a statement about the cost function rather than about the recurrence, it is a consequence of an inequality on the weights, and if it holds then the inner scan can start where one neighbour finished and stop where the other did.

The consequence is arithmetic and it is large. Summed along a diagonal the ranges telescope, so a whole diagonal costs $O(n)$ transitions instead of $O(n^2)$, and the computation drops from cubic to quadratic — filling the same cells, considering a subset of the same transitions, and returning the same tree.

Two things make that the right next rung rather than a footnote. The saving is measurable in the counter this page already reports, so the claim can be checked rather than quoted. And the property it rests on is not a property of dynamic programming at all: it is a property of the numbers in the problem, so the same recurrence over different weights is cubic or quadratic depending on something the recurrence does not mention. That is the same shape as a distance that is not a distance, where a cost matrix decides whether a structure’s pruning is sound — a property of the input deciding what is available to the algorithm, rather than the other way round.