Auxiliary space — where it appears
Named by 14 essays across 6 fields — each of them below, with the objects they name alongside it.
Measuring what an algorithm keeps
Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.
The answer that is allowed to be wrong
Every algorithm on this site so far was checked for correctness before it was measured. A summary of a stream cannot be — the data goes past once and does not fit — so the error becomes a resource, bought with bits, at an exchange rate that is a measurement.
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 frontier between time and space
The question of which sorting algorithm to use has an honest answer, and it is a shape rather than a name. Comparisons on one axis, peak auxiliary space on the other, and five of the ten algorithms here are on the Pareto frontier while five are dominated — beaten on both counts at once, so that no weighting of the two costs makes them the right choice. Heapsort is one of the five that lose.
In place is a claim, and it is usually wrong about quicksort
Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.
The space the model does not see
A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.
The table nobody has to keep
A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.
The alignment that fits in one line
Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.
The depth limit that almost never fires
Introsort counts how deep its recursion has gone and calls heapsort if it passes twice the logarithm. On every input measured, the mechanism handles under a tenth of a per cent of the elements. Then an adversary that answers the comparisons rather than choosing the array drives it to exactly n²/2 with the limit removed, and to one heapsort call with it — a factor of forty-two at n = 8,192, and growing.
What a window costs in bits
The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.
The text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
Every substring, in fewer states than substrings
A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.
The tuples a summary does not report
A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.
Named alongside it
The objects these essays reach for when they reach for this one.
Trade offCost modelQuicksortDynamic programmingEdit distanceState bitsSubproblemAllocatorCacheComparison countHonest limitMeasured count