A floor under a product

Five lower bounds have been performed here and every one of them puts a floor under a single quantity. The floor under every comparison sort counts outcomes and gets $\log_2 n!$ comparisons. A floor one pass cannot get under counts memory states and gets a number of bits. A floor that holds if something else does is a chain of implications with a conjecture at the top, and even there the thing at the bottom is one quantity.

There is a kind of bound these pages have never drawn, and it is the kind that says the most. It puts a floor under a product. A bound on time alone can be evaded by spending space; a bound on space alone by spending time. A bound on $T \cdot S$ cannot be evaded either way, because the two currencies it is stated in are the only two there are.

For sorting, the published result is $T \cdot S = \Omega(n^2)$ — Borodin and Cook’s, and a line of branching-program results after it. It is the strongest statement in this field’s literature, and the first thing the numbers here do is walk under it by a factor of four hundred.

The measurement that appears to break it #

Those are the two axes the bound is about, so the product is a multiplication away.

Read the light marks and the bound is in ruins. Heapsort sorts 8,192 elements in 187,705 comparisons with one slot of auxiliary space: a product of 187,705, against $n^2 = 67{,}108{,}864$. That is 0.0028 of a bound that nothing is supposed to get under, and shellsort is lower still.

Five of the ten sorts are under $n^2$ on that reading and the other five are above it for a reason that has nothing to do with the bound — insertion, bubble and selection sort are quadratic in time, so their products are quadratic even at one slot.

What the model forbids #

The bound is not wrong and the measurement is not wrong. They are about different machines.

The model the bound is proved in has three features, and the third is the one that matters here.

The input is read-only. It may be read as often as the algorithm likes and never written.

The output is write-only and produced in order. An output cell, once written, cannot be read back, so the output is not storage.

S is every cell the algorithm has between those two, and $T$ is every step it takes.

Every sort measured here writes to the input array. That is what “sorts in place” means, and in place is a claim is the page that made the phrase into a number: heapsort’s peak auxiliary space really is one slot, quicksort’s is $\Theta(\log n)$ of stack, merge sort’s is $\Theta(n)$, and the vocabulary has one word for all three. What none of those measurements says is that the array being sorted is itself working memory. Heapsort keeps its entire state in the input array. It has one slot of auxiliary space and $n$ cells of space.

Count it the way the bound counts it and the dark marks are what comes out. Nothing is under $n^2$: the lowest is quicksort with a random pivot at 14.8, and heapsort is at 22.9.

The rewriting is not a technicality that could be argued either way. An algorithm that writes to the input has destroyed it, and a caller that wanted the original back must have kept a copy — $n$ cells, somewhere, whoever is paying. The read-only model is not a restriction invented to make a theorem provable; it is the model of a sort whose input is a file, a shared page, or a column somebody else is also reading. Sorting what will not fit is where an input’s immovability last had to be taken seriously, and it reached the same conclusion from the other direction: once the data cannot be held, what an algorithm may do to it becomes part of its cost.

That is the whole resolution, and it is worth being precise about what kind of resolution it is. It is not that the bound has an exception, or that it applies asymptotically and these sizes are small. It is that the quantity that has been called “space” since the field opened is auxiliary space, which is the right quantity for the question “does this algorithm need a buffer”, and is not the quantity any time–space bound is about.

Performing the model #

A bound stated in a model nothing inhabits is a bound that cannot be checked. So the model is inhabited: a sorting algorithm that reads an input it may not write, emits its output in order to a stream it cannot read back, and has $S$ cells in between.

The natural algorithm in it is a scan. Keep the $S$ smallest values strictly above the last one emitted; at the end of the scan emit them in order; scan again. It needs $\lceil n/S \rceil$ scans of $n$ reads.

The product is not fitted. It is

$$T \cdot S \;=\; \left\lceil \frac{n}{S_{\text{buffer}}} \right\rceil \cdot n \cdot (S_{\text{buffer}} + 3) \;=\; n^2\left(1 + \frac{3}{S_{\text{buffer}}}\right),$$

where the three extra cells are the value and index the algorithm stopped at and its loop counter. They are counted rather than rounded away, because a bound on $S$ is a bound on every cell — and at one cell of buffer they are three quarters of the space, which is why the product there is 4 $n^2$ rather than 1.

Four sizes, one curve. The multiple of $n^2$ depends on the buffer and not at all on $n$, which is the signature of a quantity that is exactly $n^2$ times something. A fit would have produced four nearly-coincident curves and an argument about whether the difference mattered; the closed form produces one curve and the measurement agrees with it to fifteen digits.

That the family never quite reaches the bound is the right shape rather than a shortfall. A lower bound that some algorithm sat exactly on would be a lower bound with nothing left to say about bookkeeping, and the three cells are the bookkeeping.

Why a scan is the right algorithm here #

The family is a scan, and it is worth saying why nothing cleverer is available, because “the obvious algorithm meets the bound” is a suspicious sentence.

With $S$ cells and a read-only input, the only thing an algorithm can carry from one moment to the next is the contents of those cells. Whatever it has learned about the input by step $t$ is compressed into $S$ cells, which is $S\lceil\log_2 n\rceil$ bits. Between two consecutive outputs it must therefore establish which value comes next, and the only way to be certain that no smaller unemitted value exists is to have looked at every position since the last time it could rule them out.

That is the shape of the counting argument, and it is the same shape as every other floor here: a bound on what can be distinguished by a bounded amount of state. A floor one pass cannot get under made it concrete at small size by producing the collision — nine hundred and twenty-four prefixes through a nine-bit state — and the same construction one level up is a branching program of width $2^S$, which is where the published proof lives and where this page stops.

What the family does add is the other half of a tightness claim. A lower bound and a matching algorithm are two different things and only the second can be performed here. The scan is that second thing: it says the exchange rate the bound describes is real and available, not merely unbeatable.

Where this leaves the site’s other floors #

Five floors have now been drawn and they are not the same kind of object. Setting them beside each other is the point of having five.

A floor on outcomes. $\log_2 n!$ comparisons, because a comparison has two answers and there are $n!$ orderings. It is about the problem and holds for any algorithm in the comparison model, however much space it has.

A floor on states. An exact one-pass distinct-counter needs enough memory states to distinguish every prefix it might have read. It is about space at a fixed number of passes, and it was performed by exhaustion at twelve keys.

A floor with a conjecture over it. A conditional bound, whose performable half was checked over 55,754 formulas and whose other half is quoted.

A floor on a model’s own terms. The entropy of a stream under a stated model — a floor that moves when the model does, which the model is the compressor demonstrated by producing five correct floors for one stream.

And a floor on a product, which is this one. It is the only one of the five that cannot be read as a statement about a single resource, and it is the only one whose model excludes every algorithm measured here.

The last point is the one worth carrying. Four of these floors can be checked against the runs here directly. This one cannot, and the reason is not that it is harder — it is that its model and the counted array here disagree about what memory is. A bound and a measurement that disagree by four hundred times are almost never both about the same machine.

Both on one pair of axes #

On logarithmic axes a constant product is a straight line of slope −1, so “the bound is a trade” stops being a sentence and becomes a shape. The family runs down that line. The sorts sit fifteen to twenty-six times above it, in a vertical stack at $S = n$, because an in-place sort does not have a space parameter at all — it has exactly one operating point, and it is the point where the whole input is working memory.

The gap between the stack and the line is the interesting quantity and it is not waste. An in-place sort spends its $n$ cells buying $n \log n$ time instead of $n^2/S$ time; at $S = n$ the family’s own formula gives $T = n$ reads, which is fewer than $n \log n$ — but the family at $S = n$ is not sorting, it is copying, because with $n$ cells the first scan holds everything. The two are not comparable at that end. They are comparable in the middle, and in the middle the family wins the product and loses the time by a factor of fifty.

That is exactly what a bound on a product is for. It does not say which algorithm to use. It says that no algorithm gets both, and it prices the exchange: halving the cells doubles the reads, everywhere along the line, forever.

It also explains a feature of the Pareto plate at the top that looked like an accident. Five of the ten sorts are dominated there — beaten on comparisons and on auxiliary slots at once — and being dominated ought to be rare among algorithms people actually wrote. It is not rare because auxiliary slots is not the axis the trade happens on. On the axis the trade happens on, the in-place sorts do not span a range at all: they are one point, $S = n$, and they differ only in time. The frontier that plate draws is a frontier in a space where nine of its ten points have the same coordinate on one axis, and the tenth is merge sort at $2n$.

A trade-off needs a knob, and none of these algorithms has one. The read-only family does, which is what makes it a family rather than an algorithm, and it is the only thing on this page that can answer the question of what happens when half the memory is taken away.

Which claim survives, and in which model #

The bound is a theorem about branching programs, and this page has measured a family and ten algorithms. Neither of those is a proof and the page does not claim one. What has been established is narrower and worth stating exactly.

The bound cannot be checked against the usual space number here. The auxiliary-slot accounting reports products four hundred times under $n^2$, and does so for reasons that are correct about auxiliary space and silent about the model.

Once the accounting matches the model, nothing measured is under the bound, and the closest is fifteen times above it.

A family that genuinely inhabits the model reaches the bound to within a factor of $1 + 3/S$, which goes to one. So the bound is tight in the sense that matters for reading it: it is not a floor nobody approaches.

What is not established is the bound itself. Proving $T \cdot S = \Omega(n^2)$ needs an argument about every algorithm in the model rather than the best one anybody wrote, and that argument is a counting argument over branching programs of a stated width — the same shape as a floor one pass cannot get under’s pigeonhole, one level of abstraction higher and past what can be performed here. It is quoted, and quoted as quoted.

What is settled and what is not #

Settled, at n = 8,192, counted exactly: under peak-auxiliary-slot accounting five of ten sorts have a time–space product below $n^2$ — shellsort at 0.0024, heapsort at 0.0028, the three quicksorts between 0.0498 and 0.0663. Under the accounting the published bound uses, with the input array counted as the working memory it is, the same ten range from quicksort’s 14.8 $n^2$ to selection sort’s 4,096, and none is below $n^2$.

Settled, by construction and by measurement at four sizes: a sort with a read-only input, a write-only output and $S$ cells has $T \cdot S = n^2(1 + 3/S)$ exactly, agreeing with the measurement to twelve decimal places and independent of $n$.

Not settled:

The bound. It is quoted, not proved, and the model it is proved in is a branching program rather than the counted array these measurements run on. The family above shows the bound is reachable; it says nothing about whether it is a floor.

Other problems. The $\Omega(n^2)$ is for sorting. Selection — producing one output rather than $n$ — has a much weaker bound, which is why what a second pass buys could find a median in eleven thousand bits and two passes without contradicting anything here.

A family that is not a scan. The one measured is the obvious algorithm in the model and it meets the bound, so nothing here can distinguish “the bound is tight” from “this algorithm is optimal”. A better algorithm in the same model would have to beat $n^2$, which the bound forbids — so the interesting question is whether a worse one is ever preferable, and the reads here are sequential, which the bound does not reward and a machine would.

Bits against cells. The space is counted in cells of $\lceil \log_2 n \rceil$ bits. The published bound is usually stated with $S$ in bits, which multiplies every product here by thirteen at this size and changes nothing about the ordering — but it would change the constant in the closed form, and this page has not checked which convention the quoted result uses.

Still open: the product when the reads have to be paid for #

The family’s reads are sequential — it scans the input from one end to the other, $\lceil n/S \rceil$ times — and the sorts it is compared against are not. Where an algorithm looks drew that difference as a picture and one access, eight kilobytes priced it: the same number of accesses costs 1,024 transfers in one order and 65,536 in another.

That is a second product, and the bound says nothing about it. A scan of $n$ elements costs $n/B$ transfers and a quicksort partition costs about the same, but heapsort’s spray costs one transfer an access. So in transfers rather than reads the family’s $T$ falls by a factor of $B$ and heapsort’s does not, and the vertical stack on the last plate would stretch out.

The measurement that follows replays the family’s accesses and every sort’s through the block model the transfer field uses, at a stated block size, and recomputes the product in transfers times cells. The prediction is that the family’s advantage widens from fifteenfold to something near $B$, and that the ordering among the sorts changes — because the three quicksorts sit within a factor of 1.1 of each other in reads and are known to differ in locality. If that holds, then a bound on $T \cdot S$ in a model with unit-cost reads is a bound about the wrong $T$ for any machine with a memory hierarchy, which is the same complaint the count is not the time makes about every other count here.