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 4 essays across 3 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

Named alongside it

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

Cost modelDynamic programmingSubproblemAuxiliary spaceEdit distanceKnapsackMeasured countComplexity classEvaluation orderOverlapping subproblemsPseudo polynomialRecurrence

All concepts