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

Machine word — where it appears

The unit a processor reads and operates on at once, thirty-two or sixty-four bits wide. It is the unit in which several structures here are genuinely constant while being unbounded in positions, because one instruction inspects a whole word.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

—sitting—kitten111111101111110-1111110-1-111110-1-1-11110-1-1-10110-1-1-10-11one unit = one subproblem given a value-1, 0, 1 — 3 values, 2 bits each

A column computed in machine words

Adjacent cells of a distance table differ by at most one, so a whole column is two bits per cell — and thirty-two of them fit in one register. Fifteen word operations per character replace three cell evaluations per cell, and below a pattern of fifteen characters the trade is a loss.

machine · Machine 1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k

Select is not rank backwards

Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.

machine · Index

Named alongside it

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

Bit-parallelBit vectorBranchlessCarry propagationConstant timeCost modelCrossoverDensityDirectoryDynamic programmingEdit distanceLocality

All concepts