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

Overlapping subproblems — where it appears

The property that a recursion reaches the same subproblem along many routes, without which a table records answers nothing ever asks for again. Without it a table is pure overhead, so the property is the precondition under which the whole method is worth applying at all.

Named by 3 essays across one field — 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 01234567891011120123456789101112123456789101112123456789101112345678910123456789123456781234567123456123451234123121one unit = one subproblem given a value91 cells, 364 transitions, 4.0 per cell

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.

tables · Table

Named alongside it

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

Cost modelDynamic programmingMeasured countRecurrenceSubproblemAuxiliary spaceComplexity classEdit distanceMemoisationRecursionCall stackComparison count

All concepts