The argmin that cannot go backwards

The previous rung ended on a question rather than a result. An interval table’s cell considers every split point inside its own interval, that is where the cubic comes from, and nothing in the counter says whether all those candidates need examining.

They do not, and the reason is a sentence about the weights rather than about the algorithm: the split point that wins for an interval cannot lie to the left of the one that wins for the interval with one fewer key on the right, nor to the right of the one that wins for the interval with one fewer key on the left. Written down that way it sounds like bookkeeping. It removes a factor of $n$.

It is worth being clear about what is and is not being claimed, because the sentence is easy to over-read. Nothing is skipped. Every cell is still filled, every cell still gets the same number, and the tree that comes out is the same tree — the gate holds all three of those to equality at every size. What changes is the set of candidates each cell examines on the way to its number, and the claim is that the candidates outside a certain window cannot win. A search that never examines a losing candidate has lost nothing.

What the property says, and what it is a property of #

Write $K(i, j)$ for the split point that achieves the minimum for the interval $[i, j)$, choosing the leftmost when several tie. The claim is

$$K(i, j-1) \le K(i, j) \le K(i+1, j)$$

for every interval, and both neighbours are intervals one key shorter — so by the time $[i, j)$ is filled, both bounds are already sitting in the table.

The inner loop then runs from $K(i, j-1)$ to $K(i+1, j)$ instead of from $i$ to $j-1$. On any single cell that might save nothing at all. Across a whole diagonal it telescopes: the lower ends are non-decreasing and the upper ends are non-decreasing, so the total length of all the ranges on one diagonal is at most $n$ plus the number of cells on it. A diagonal costs $O(n)$ transitions rather than $O(n^2)$, there are $n$ diagonals, and the computation is quadratic.

The important word in the claim is weights. The monotonicity is not true of interval recurrences in general; it is true when the weight function satisfies a quadrangle inequality — informally, that widening an interval on both sides costs at least as much as widening it on each side separately. A range’s total frequency satisfies it. Plenty of other weight functions do not, and for those the same recurrence over the same triangle really is cubic.

So this is the sharpest instance in the field of a rule this collection keeps meeting: a property of the numbers decides what is available to the algorithm, and the algorithm’s description does not contain the numbers. A distance that is not a distance is the same shape from the other side — there a cost matrix removes a guarantee a structure was relying on, here a weight function grants a shortcut nobody could see in the recurrence.

The telescoping is worth doing slowly once, because it is the whole of the saving and it is short. Fix a diagonal — all the intervals of length $\ell$ — and walk it left to right. Cell $[i, i+\ell)$ searches from $K(i, i+\ell-1)$ to $K(i+1, i+\ell)$. The next cell along searches from $K(i+1, i+\ell)$ to $K(i+2, i+\ell+1)$, and its lower bound is the previous cell’s upper bound. So the ranges are consecutive intervals of a non-decreasing sequence, they overlap only at endpoints, and their total length is at most the sequence’s whole span — which is $n$ — plus one per cell for the endpoints. That is $O(n)$ per diagonal against $O(n^2)$, and it is the entire argument.

The saving, measured #

The two fills are the same code with two lines changed, and both are run on the same weights at every size.

The cell column is identical down the table, which is the check that matters. A version that skipped cells would evaluate less and answer differently; a version that narrowed the range by a constant would save a constant. Here the cells agree exactly, the answer agrees exactly, and the ratio doubles every time the key count doubles — which is a factor of $n$ and not a factor.

The ratio is not $n/1$ but roughly $n/6.7$, and the constant is worth a sentence rather than a shrug. The monotone version still pays one transition per cell even when the range collapses to a single candidate, so its cost is $\Theta(n^2)$ with a constant near one, and the cubic version’s cost is $n^3/6$ because the average interval is $n/3$ long. The measured ratio is the quotient of those two, and it agrees.

What that ratio does to the reachable problem size is the practical point. A cubic fill over a thousand keys is about $1.7 \times 10^8$ transitions, which is a few seconds and is fine; over ten thousand it is $1.7 \times 10^{11}$, which is not. The quadratic fill over ten thousand is $10^8$, back to a few seconds. The optimisation does not make a computation faster so much as it makes a size available, and the sizes it makes available are the ones a real key set has. That is the same distinction the table nobody has to keep draws about space: past a certain point a resource is not a cost that trades against another, it is a gate.

Why the bounds are already in the table #

The elegance of the method is that it needs nothing stored beyond what it is already computing.

Filling by increasing interval length, the cell $[i, j)$ is reached after every shorter interval. Its two bounding neighbours, $[i, j-1)$ and $[i+1, j)$, are both exactly one shorter. So the argmin table — one integer per cell, the same triangle again — is available in full, and the lookup is two array reads.

That costs a second table of $n^2/2$ integers, which is the entire price. In the accounting this field keeps, the monotone version has the same cell count, roughly twice the space, and a third fewer transitions at eight keys rising to a thirty-eighth at two hundred and fifty-six. It is the rare case where the space cost is a constant factor and the time saving is a factor of $n$, and it is worth naming as rare, because most of the trades in this field go the other way — the table nobody has to keep buys a factor of $n$ in space and gives up the traceback to get it.

The fill order is also forced rather than chosen. Row order does not work here: filling $[i, j)$ before $[i+1, j)$ leaves one bound missing. The previous rung noted that an interval table has one degree of freedom in its order where an edit-distance table has three, and this is what the freedom was spent on — the order that makes the bounds available is the same order the dependencies already required, so the optimisation is free of any scheduling cost. That is worth contrasting with the rectangular case, where the same table, filled two ways found three valid orders and had to choose between them on other grounds; here there is one order and it happens to be the one this rung needs.

What it costs to have found this #

Two of the three problems in the previous section were solved by somebody who already knew this trick, and the third — the alphabetic tree — was solved twice, once cubically and once quadratically, four years apart. That gap is the ordinary situation for a result of this kind and it is worth understanding why.

The recurrence is the same on both sides of the improvement. The table is the same. The answer is the same. Nothing about the program suggests that a smaller search would do, because the program’s text contains no information about the weights: it takes an array of numbers and consults them. The evidence that the range can be narrowed lives entirely in an inequality about what those numbers can be, and that inequality is not written anywhere the program can see.

This site has a name for the general case — the cost model is an input — and this is its sharpest instance. Most of the time a cost model decides what the answer is. Here it decides what the algorithm is allowed to skip, and the same source code is cubic or quadratic depending on a fact about the caller’s data that no type signature and no test could express.

What the check has to rule out #

An optimisation that produces the right answer for the wrong reason is the ordinary failure here, and there are two obvious ways to get one.

The bounds can be transposed. Taking $K(i+1, j)$ as the lower end and $K(i, j-1)$ as the upper is one character different, it is what the rule looks like when it is remembered rather than derived, and it produces a range that is usually empty or backwards. Fed that version, the same weights that give a tree of weighted cost 12,689 give 70,406 — a factor of 5.5, and an answer rather than a crash. The gate performs exactly that transposition and requires the wrong answer, because an optimisation whose failure mode is silent needs a test whose failure mode is not.

And the property can be assumed rather than held. Nothing in the code checks that the weights satisfy the inequality; the code narrows the range and trusts. On weights that do not satisfy it, the narrowed range can exclude the true optimum, and the computation returns a tree that is not the best one and no indication that anything happened. That is a genuine hazard and it is the reason this optimisation is described in the literature with its precondition attached and implemented in practice without it.

The general form of that second hazard is worth stating, because it is the one this collection is most concerned with. An optimisation with a precondition has two failure modes and only one of them is visible. If the precondition is checked and fails, the program falls back and is slow. If it is not checked and fails, the program is fast and wrong, and nothing distinguishes its output from the right answer except knowing the right answer. The bound with a precondition makes exactly this point about a shortest-path algorithm on a graph with a negative arc — the answer that comes back is a number, it is plausible, and it is wrong on four vertices — and the shape here is identical with weights in place of arc costs.

The reason implementations ship it unchecked is also worth naming rather than tutting at. Verifying the quadrangle inequality directly means checking a condition over every quadruple of indices, which is $\Theta(n^4)$ — vastly more than the cubic fill the optimisation was meant to avoid. So there is no cheap check, only a proof about the particular weight function, and a proof lives in a paper rather than in a program. The precondition is unverifiable at run time in any useful sense, which is a real reason for its absence and not an excuse for it.

What else the same rule reaches #

The property is not about search trees. It holds for a family of problems whose weight functions satisfy the same inequality, and three of them are worth naming because they are the ones people meet.

The optimal alphabetic tree — the same problem with the constraint that the keys keep their order in the tree, which is the case here.

A one-dimensional partition into $k$ pieces minimising a convex cost, which is what a histogram builder, a text justifier and a segmented regression all reduce to. The same telescoping applies along the piece index rather than along an interval length.

And the shortest-path formulation of a sequence alignment with a concave gap penalty, where the same argument gives $O(n^2 \log n)$ in place of $O(n^3)$ by a slightly different mechanism. That one sits directly beside a cell that has to know where it is, which reaches an affine gap by carrying three tables; a concave penalty cannot be reached that way at all, and the monotone argument is what makes it tractable instead.

What none of them shares is the recurrence’s shape, and that is the point worth carrying. These are not all interval dynamic programs. They are problems whose cost functions have a common property, and the property is what the optimisation attaches to. A technique that attaches to a property of the input rather than to the form of the recurrence is one nobody finds by staring at the loops, which is why it took until 1971 for this one to be written down and why it is absent from most implementations that would benefit.

There is one more reading of this rung that is worth having, and it connects to how this site grants classes at all. Every complexity claim here is fitted to measurements across three orders of magnitude and granted only if the fit holds, which is the discipline fitting a class to measurements sets out. Apply that discipline to the two fills and something slightly awkward appears: both of them fit something, the cubic version fits $n^3$ and the quadratic version fits $n^2$, and the fitting procedure has no way of knowing that the second one’s class depends on a property of its input.

Feed the same code weights that break the inequality and it will still fit $n^2$ — it will still narrow the range, still run quadratically, and still return an answer. The fit would be perfect and the answer would be wrong. A measured class is a statement about the runs that were measured, and where the class depends on a precondition, the sweep has to be run on inputs that satisfy it and on inputs that do not, or the fit is evidence about the generator rather than about the algorithm.

What the counter still cannot see #

Two limits, and the second matters for anyone reading the ratio as a speedup.

A transition is one unit. The monotone version does slightly more work per candidate — two extra array reads to fetch the bounds — and the counter charges nothing for those. At a range of one candidate that overhead is a third of the cell’s cost, so the quadratic version’s constant is worse than the count suggests, and the crossover where it starts winning is a little later than the table implies. At sixteen keys it is already ahead by a factor of three, so nothing on the plate changes; at four keys it would not be.

The weights are a range sum and nothing else was tried. Every measurement here uses frequencies summed over an interval, which satisfies the inequality for a short and general reason. A weight function that satisfied it for a subtler reason, or that satisfied it only on some inputs, would be the interesting test case — and there is none on this page, so the plates are evidence that the optimisation works where it is known to work rather than evidence about its boundary. One run, four counts, four answers is the standing reminder that a measurement on one input family is a measurement of that family.

And the space is not counted here at all. The argmin table doubles the memory, and this field’s counter reports cells given a value rather than bytes allocated. That is the same gap measuring what an algorithm keeps exists to close for arrays, and it is not closed for a second table of integers sitting beside the first.

Where this ladder goes from here: the order that has a depth #

Every fill on this page and the last is a sequence: one cell, then the next, in an order the dependencies permit. The count of transitions is a total over that sequence, and a total says nothing about what had to wait for what.

A table is the one place in this collection where that second question has an exact answer that needs no model of a machine. The recurrence is a directed acyclic graph over the cells; its longest path is the number of rounds that no amount of parallel work can get under; and a given fill order achieves some number of rounds between that path and the cell count. Three numbers of one computation, all of them integers, all of them the same on every machine.

The interval table’s own answer is worth having, because the length-ordered fill it is forced into is exactly a wavefront: every cell on the diagonal of length $\ell$ depends only on shorter ones, so a whole diagonal is independent and the depth is $n$ against a cell count of $n^2/2$. This rung’s optimisation does not change that at all, and the fact that a factor-of-$n$ saving in transitions leaves the depth untouched is the clearest possible argument for measuring the two separately — which is the next rung, taken on the rectangular table where the three orders can be compared.