Recurrence — where it appears
Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.
The cost is the number of subproblems
The edit-distance recurrence, written down literally, makes 29,737 calls on a six-letter word and a seven-letter word. Written down with a table beside it, it makes 56. Nothing about the arithmetic changed, and the class did.
The same table, filled two ways
Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach.
The cells are not the cost
This field opened by pricing a dynamic program in subproblems — 29,737 calls became 56 cells and the class changed. That is right when a cell is cheap. A table over intervals has 8,385 cells and considers 349,504 transitions to fill them, and the cubic in its bound is inside the cell rather than in the table.
The argmin that cannot go backwards
The same triangular table, the same ninety-one cells, the same tree at the end of it — and 364 transitions one way against 156 the other. At 256 keys the ratio is 38. What removes the factor is not a property of the recurrence but a property of the numbers it is given, and the recurrence does not mention them.
The order that has a depth
One hundred cells, filled in three orders, producing one table. Row order takes ninety-one steps and anti-diagonal order takes nineteen. Nineteen is not a property of the order — it is the longest chain of cells in the recurrence itself, no schedule can get under it, and every count taken until now was a total that could not see it.
A distance divided by a length is not a rate
Two substitutions turn "ab" into "ba", a distance of two over an alignment of two columns — a rate of 1.00. Deleting, matching and inserting also costs two, over three columns, for 0.67. Both are alignments of the same pair, the second has the better rate, and the optimal alignment is not the one that achieves it. Over every pair of strings up to three characters on three letters, 21% disagree.
The edit that reaches back two rows
Swapping two adjacent characters is one keystroke and costs two edits. Adding it as a fourth transition is four lines, it is what nearly everything ships, and the function those four lines compute is not the one they are named after. Over 1,600 pairs of short strings the two definitions differ on twelve, and the shipped one breaks the triangle inequality on twelve triples where the other breaks it on none.
The cells that were never worth having
Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.
A distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate on this site reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
Named alongside it
The objects these essays reach for when they reach for this one.
Measured countDynamic programmingCost modelSubproblemEdit distanceComplexity classOverlapping subproblemsAuxiliary spaceComparison countEvaluation orderHonest limitInterval dp