Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Memoisation — where it appears

Recording a subproblem's answer the first time it is reached so later arrivals read it, which changes a recursion's class without changing its arithmetic. It changes the class and not the arithmetic, which is why an exponential recursion and a linear one can differ by a single dictionary lookup.

Named by 8 essays across 4 fields — each of them below, with the objects they name alongside it.

—bcab—abca6388328188632571322513518753111111one unit = one invocation of the recurrence481 calls, 25 distinct subproblems

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.

tables · Table —sitting—kitten012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455one unit = one subproblem given a value56 cells, filled in row order

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.

tables · Table —execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once

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.

space · Table 10³10⁴capacity Wsubproblems given a valueBottom-up table · 1.00Top-down, reachable only · 0.14one unit = one subproblem given a valuesubproblems given a value, W from 200 to 3200

A table wider than its input

The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.

wrong · Bound 1248163264rows in the ringshare of the table's skipped comparisons0%25%50%75%100%256 keys1,024 keys2,048 keysselection sort, random keysticks: expected minima a pass

A record the size of a pass's minima

Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.

counting · Count 1282565121,0242,0484,096keys sorted, ntable's skips caught94%96%98%100%the chain of the last passa ring of twelve rowsrandom keys, every answer checkedring: the earlier record, LRU

A record of stretches, not pairs

Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.

counting · Count 1282565121,0242,0484,096keys sorted, nrepeats answered94%96%98%100%minimum chain, its own repeatsmaximum chain, its own repeatsone-sided sort's chainrandom keys, every answer checkedeach share of its own side's repeats

Two swaps a pass, and the stretches hold

Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.

counting · Count 1282565121,0242,0484,09610³10⁴10⁵10⁶keys sorted, ncomparisons madethe two chainschains and runssorted keys, every answer checkedruns: adjacent positions of known order

A run answers what nobody asked

Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Measured countComparison countCost modelDynamic programmingPredictionSelection sortSpace time tradeSubproblemWorking setAuxiliary spaceEdit distanceKnapsack

All concepts