Bound — the series
-
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.
-
The constant the notation drops
Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.
-
A limit is not a prediction
Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.
-
The depth limit that almost never fires
Introsort counts how deep its recursion has gone and calls heapsort if it passes twice the logarithm. On every input measured, the mechanism handles under a tenth of a per cent of the elements. Then an adversary that answers the comparisons rather than choosing the array drives it to exactly n²/2 with the limit removed, and to one heapsort call with it — a factor of forty-two at n = 8,192, and growing.
-
A table wider than its input
The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.
-
The model a bound was quoted in
Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.
-
A floor that holds if something else does
The four lower bounds written before it are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.
-
A floor under a product
Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.
-
A product paid for in blocks
The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.
-
The memory a product does not charge
Time times space charges a sort for the cells it writes and not for the fast memory it needs to write them cheaply. Counted three ways, on random keys in lines of eight, a read-only family stays within a factor of eight of the floor with 32 to 256 cells of fast memory at every length, while heapsort needs all of n and quicksort an eighth of it. Quicksort's need falls far faster than predicted as the factor loosens. And the product the floor leaves out, transfers times fast memory, separates the two kinds of sort completely: no read-only sort can push it far below n²/B, and quicksort reaches a twentieth of it.
-
The lines a sort writes back
A replay that charges a transfer for every line brought into fast memory and none for a line sent back flatters every sort that writes in place. Charged for its write-backs, quicksort's transfers rise by 1.9 at every memory short of n, as predicted, and heapsort's by 1.8, not the predicted three, because no line can go back more often than it came in. The cost that changes the account is the last one: at n itself every in-place sort pays two reads of its array, so none of them can come within a factor of two of the floor, while the read-only family reaches 1.07.
-
A buffer that does not shift its tail
The read-only family of sorts scans its input once for each batch of the smallest values not yet output, keeping them in a buffer; charged for the dirty lines it sends back to slow memory, its least transfers × fast memory rose from 1.29 of n²/B to 1.87, because a sorted buffer takes each value by shifting every larger entry one place. Kept as a max-heap instead, the buffer was predicted to write back about a third of the lines it reads below its own size and to bring the product back towards 1.29. At a buffer of 64 cells it writes back 33% at its best memory, against 45%, and its least product falls to 1.71: right about the share, wrong about the product, since a third written back is still a third more transfers. At 256 cells the heap does more than predicted — 1.47 million accesses against 6.94 million, a third of the misses — and its least product, 1.62, is under any buffer's on the earlier charge. At 16 cells it does nothing.