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

Time space tradeoff — where it appears

A frontier along which an algorithm may spend more of one resource to spend less of the other, with no dominant point on it. There is no dominant point on it, so choosing one is a decision about the deployment rather than a fact about the algorithm.

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 pale: total slots ever allocated · dark: peak held at onceone buffer, allocated once16,38416,400peak 100% of na buffer per merge229,37616,386peak 100% of nn = 16,384, random input208,687 comparisons each — identical in time

The space the model does not see

A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.

space · Space cells expandedreads building the estimateNo estimate1,572 expanded · path 356Straight-line estimate1,550 expanded · path 356A*, landmarks252 expanded · path 356 · 6,328 reads to buildV = 2,500, steps cost one to nine, seed 20260910shortest path 356

An estimate borrowed from an easier problem

On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.

graphs · Graph 10,000110sampling, bitssteps per occurrence1 in 21 in 41 in 81 in 161 in 321 in 641 in 128r-indexEnglish-like · 16 copies · r = 233pattern " time "

Every occurrence at the same price

A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.

space · Repeat

Named alongside it

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

Pareto frontierAllocatorTrade offAdmissibilityAmortised analysisAuxiliary spaceBranching programBreak-evenCacheComparison countCost modelCounting sort

All concepts