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

Tight bound — where it appears

A bound that is achieved rather than merely respected, so that the distance between it and the best algorithm is zero rather than unknown. The distance between it and the best algorithm is zero rather than unknown, which is a much stronger statement than a bound nothing has yet beaten.

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

10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly

What O-notation does not say

Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it.

bounds · Bound 10⁴10010³n (elements)block transfersmeasured sortthe bound3.20×2.67×2.29×2.94×2.67×2.40×B = 32, M = 512 (M/B = 16)3.20× the floor at worst

The floor under moving data

The information-theoretic floor for comparison sorting is log₂(n!) and it says nothing about a file on a disk. In the external model the floor is (n/B)·log_{M/B}(n/B), it is a bound on every algorithm rather than on merge sorts, and a measured external sort sits 2.40 to 2.97 times above it. Both numbers are computable, and the gap between them is what a real implementation costs.

floors · Floor key 16,726exactkey 23,236exactkey 32,035exactkey 41,440± 2key 3109± 937key 42117± 937key 8402± 937key 14914± 937bracket, with the truth marked · widest 937 · 3 exactcash register · stationary Zipf · 32 countersthe smallest counter is 938

The counter that takes the smallest slot

Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.

structures · Sketch

Named alongside it

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

Asymptotic notationBlock transferComparison countConstant factorCount-MINCounting argumentDistributionExternal-memory modelExternal merge sortGuaranteeHeavy hitterInformation-theoretic bound

All concepts