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

Constant time — where it appears

A cost that does not grow with the input's size, which is a statement about growth and not about magnitude. A constant-time range-minimum query is nine or ten memory accesses here, and that number is what decides where it crosses a method whose cost does grow.

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

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 0000200121200the parenthesis sequencethe minimum excess of each block of 213 blocks · lookup table 72 bits, sharedblock 2 · 24 parentheses13 blocks

The table that fits inside a block

A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.

machine · Range

Named alongside it

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

MeasurementSpace overheadTrade offBit vectorBlock decompositionCartesian treeConstant factorDensityDirectoryLookup tableMachine wordRange minimum

All concepts