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

Recursion — where it appears

A procedure that calls itself on smaller inputs, holding one frame per level, which is a cost the equivalent loop nest does not pay at all. Its frames are auxiliary space that no array counter sees, and a deep one exhausts a real stack long before its table runs out of room.

Named by 5 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—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held

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.

space · Distance cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells

The split scan cut into blocks

Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.

tables · Table range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

A document already in the answer

The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.

structures · Index

Named alongside it

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

Dynamic programmingAuxiliary spaceEdit distanceSubproblemCall stackCost modelDivide and conquerEvaluation orderMeasured countMemoisationOverlapping subproblemsRecurrence

All concepts