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

Growth factor — where it appears

The multiple by which a dynamic array resizes, which sets both the amortised cost per append and whether freed blocks can ever be reused. It sets both the amortised cost per append and whether freed blocks can ever be reused, which is why the shipped values are not the one the arithmetic suggests.

Named by 4 essays across 3 fields — each of them below, with the objects they name alongside it.

0%25%50%75%12345×1.125×1.25×1.5×2×3×4capacity left unused at the endamortised cost per append20,000 appends, cost = 1 write + a copy on resizeneither end wins

Choosing a growth factor

When a dynamic array fills up, how much bigger should the new one be? Doubling costs 2.02 units per append and leaves 39% of the allocation empty. Growing by an eighth costs 9.89 and leaves 10%. Every factor is a trade between time and space, no factor wins on both, and real implementations disagree about the answer for reasons that are measurable.

structures · Structure 10⁵10⁶10⁷11010010³10⁴comparisonspeak auxiliary slotsInsertion sortSelection sortBubble sortMerge sortHeapsortQuicksortQuicksortQuicksortShellsortMerge sort with a cutoffn = 8,192, random input5 on the frontier, 5 dominated

The frontier between time and space

The question of which sorting algorithm to use has an honest answer, and it is a shape rather than a name. Comparisons on one axis, peak auxiliary space on the other, and five of the ten algorithms here are on the Pareto frontier while five are dominated — beaten on both counts at once, so that no weighting of the two costs makes them the right choice. Heapsort is one of the five that lose.

space · Space 0.01%0.1%1%10%100%1,0002,0003,0004,0005,0006,0007,0008,000keys insertedabsent keys answered yesone filterm = 19,171, k = 7; dotted: the design sizedashed: the design rate

A filter past its design size

A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.

randomness · Randomness 0.01%0.1%1%10%100%1,0003,0005,0007,0009,00011,00013,00015,000keys insertedabsent keys answered yesone Bloom filtera stack of Bloom filtersfingerprints, none reservedfingerprints, 3 reservedforecast 2,000, target 1.0%; dotted: the forecastdashed: the target rate

A filter that grows by moving a bit

A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.

randomness · Randomness

Named alongside it

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

Trade offAmortisedBloom filterError budgetFalse-positive rateGuaranteeLoad factorOne-sided errorPareto frontierResizingSpace overheadAlgorithm selection

All concepts