Two floors that can be added

The count of the part that was read put two floors under the problem of handing back the $k$ smallest of $n$ keys in order, and was careful to say they could not be added.

Every element not handed back must lose a comparison. Each comparison has exactly one loser, so at least $n - k$ comparisons are needed. And the answer must be distinguished from every other possible answer, which is one of $n!/(n-k)!$ sequences, so at least $\lceil \log_2 n!/(n-k)! \rceil$ comparisons are needed. Adding them would double-charge, because the comparisons that eliminate the losers also carry information, and at $k = 1$ the sum exceeds what a scan actually costs.

So that page took the larger of the two, and said where the arrangement is weak: they cross near $k = 3{,}900$, and where two arguments cross each is saying only that the other might be right. The ratio plate peaked there at 1.97 and the page left the question of whose weakness it was.

It is the floor’s. The two arguments can be added — not as they were stated, but after one of them is narrowed — and the narrowing is a sentence about which comparisons can carry which kind of work.

The sentence #

Take the $k$ elements handed back and call them the outputs. The algorithm must establish their total order: it must know which is smallest, which second, and so on.

Suppose it knows $a < b$ for two outputs. Knowledge here is the transitive closure of the comparisons made, so there is a chain

$$a < x_1 < x_2 < \cdots < b$$

of comparisons the algorithm actually performed. Every element of that chain is an output. Each $x_i$ is known to be less than $b$, so in the true order $x_i < b$; and $b$ is among the $k$ smallest, so anything smaller than $b$ is among the $k$ smallest too. A key that is not handed back is larger than every key that is, and can never stand between two of them in a chain.

So the outputs’ order is established entirely by comparisons between two outputs, and there must be at least $\lceil \log_2 k! \rceil$ of them, since they alone have to distinguish $k!$ orderings.

Now count losers. A comparison between two outputs has an output as its loser. A comparison that gives a non-output its required loss has a non-output as its loser. The two sets of comparisons are disjoint, and so

$$W(n, k) \;\ge\; (n - k) + \lceil \log_2 k! \rceil$$

is a floor. Nothing is charged twice: the first term counts comparisons whose loser is not handed back, the second counts comparisons whose loser is.

It is worth checking the sentence against the two ends, because a bound that is wrong is usually wrong at an extreme. At $k = 1$ there is nothing to order, $\lceil \log_2 1! \rceil = 0$, and the floor is $n - 1$ — which is exactly the cost of finding a minimum, so it is tight rather than merely valid. At $k = n$ nothing is eliminated, $n - k = 0$, and the floor is $\lceil \log_2 n! \rceil$ — which is the floor under every comparison sort, recovered as a special case. A combination that reproduces both known answers at the ends is at least not obviously wrong in the middle.

What it is worth #

At $k = 4{,}000$ — the crossing, where the old arrangement was weakest — the larger of the two old floors is 63,821 and the new one is 103,636, sixty-two per cent higher. At $k = 1{,}000$ it is 64,536 against 73,066; at $k = 10{,}000$, 158,839 against 173,995.

It is never lower. The new floor exceeds the loser count by $\lceil \log_2 k! \rceil$, which is not negative, and it exceeds the information count whenever $n - k$ exceeds $\lceil \log_2 \binom{n}{k} \rceil$ — which holds over most of the range on any large $n$, because identifying which $k$ elements are smallest costs far fewer bits than eliminating the rest costs comparisons. At the two ends the old arguments win and the new floor coincides with them.

The shape is the reason the old arrangement failed where it did. One term falls, the other rises, and taking the larger throws away whichever is smaller — which near the crossing is nearly half of what is available. Charging both keeps it.

What it says about the tournament #

The spike was the floor’s. A method that looked as though it might be doing twice the necessary work at one particular $k$ turns out to be within 24% of what no method can beat, at every $k$ from one to all of them.

That is worth stating in the form the earlier page asked for. It wanted to know “whether any method can hand back four thousand keys from 65,536 in substantially fewer than 125,388 comparisons”. The answer is now bounded: no method can do it in fewer than 103,636, so at most seventeen per cent of the tournament’s work at that point can be removed by any method at all, and quite possibly none of it.

The other five lines move too, and not equally. A method already far above the floor — sorting everything, at 14.7 times it for the smallest ten — is barely changed by a floor that rises 62% in the middle of the range. The bounded heap, which collapses past $k = 1{,}000$, keeps its collapse. Only the tournament, which was close everywhere except at the crossing, turns out to have been close everywhere.

Where the improvement comes from, in one number #

The two old floors and the new one can be compared term by term at the crossing, and the arithmetic says where the sixty-two per cent lives.

At $k = 4{,}000$ of 65,536 keys:

• eliminating the 61,536 keys nobody sees: 61,536 comparisons;
• ordering the 4,000 that are seen: $\lceil \log_2 4000! \rceil =$ 42,100 comparisons;
• and the information floor’s total, $\lceil \log_2 \binom{n}{k} \rceil + \lceil \log_2 k! \rceil$, is 21,721 + 42,100 = 63,821.

The two accounts agree exactly about the second term — both charge $\log_2 k!$ for the outputs’ order, because both are counting the same bits — and differ entirely about the first. The information argument charges 21,721 comparisons to identify which 4,000 keys are smallest; the loser argument charges 61,536 to eliminate the other 61,536. The second is nearly three times the first, and the old arrangement was throwing it away whenever the information total happened to be the larger of the two.

That also says why the crossing is where the loss is worst. To the left of it the loser count is the maximum and the outputs’ order is nearly free, so the old floor was already charging almost everything. To the right the information count is the maximum and it contains the outputs’ order in full, so again little is lost. Only in the middle is each account holding something large that the other does not, and only in the middle does taking the maximum discard it.

How far the new floor is from the truth #

A floor is a claim about every possible method, and the way to see how much of it is slack is to compute the truth somewhere.

The search is certified by three answers that are already known, and it agrees with all three: $n - 1$ comparisons for the smallest, $n - 2 + \lceil \log_2 n \rceil$ for the smallest two — seven, at six elements — and the sorting optimum of ten when $k$ is every element. At four elements the floor is exact at every $k$. At five and six it is short by one or two.

So the combined floor is a floor and it is not the answer, which is the honest half. Two comparisons of slack at $n = 6$, $k = 2$ is not a small share of seven, and nothing here says how that share behaves as $n$ grows. What the exact values do establish is that the slack is small and bounded at the sizes where it can be seen, which the old arrangement’s slack was not: at $n = 6$, $k = 2$ the old floor is 5 and the truth is 7.

The peak was not a property of this size #

The old peak is near two at every size and does not fall. The new one is under 1.35 at every size and does fall — 1.346 at a thousand keys, 1.235 at sixty-five thousand — which is the shape a slack that is a lower-order term should have.

That is the strongest evidence that the new floor is the right shape rather than merely a larger number. A floor that were simply an arbitrary improvement would not have a residual that shrinks with $n$; one that has captured the leading terms would.

What the earlier page could have noticed and could not #

There is a reading of all this that is unkind to the earlier page and it is worth refusing explicitly, because the refusal is the interesting part.

The sentence this page turns on — a non-output cannot lie between two outputs — is available to anyone who writes down the partial order, and it takes a paragraph. Why did the page that drew the peak not find it?

Because it was measuring methods and the peak is a property of a bound. Every plate on that page compares a method against a floor, and a plate of that shape cannot distinguish a method doing unnecessary work from a floor failing to demand necessary work. The page said so — “that peak is a statement about the floor, not about the tournament” — and then had nothing to put in the denominator.

The thing that would have settled it is the one this page ran: compute the truth somewhere. At $n = 6$, $k = 2$ the old floor is 5 and the optimum is 7, so the old floor was known to be loose before any new argument existed. A single exhaustive computation at a size small enough to afford it converts “one of these two is at fault” into “the floor is at fault, by at least this much” — and it needs no insight at all, only the patience to write a minimax.

That is the transferable habit, and it is cheaper than the insight it replaces: writing a minimax over sets of orderings took less care than proving the chain sentence, and it is the half of the work that could have been done first. The worst case found by climbing is the same move in the other direction: a search certified at eight elements, where every answer can be checked, and then run where it cannot.

What a floor is for #

The whole exercise is a demonstration of something that recurs everywhere a lower bound is quoted and is rarely stated so cleanly.

A lower bound is a claim about every possible method, and a weak one is indistinguishable from a method being bad. The earlier page reported a method at 1.97 times its floor and could not say which of the two was at fault. It said so, which is the right thing to do with a number one cannot attribute — and the attribution turned out to be entirely on one side.

And two arguments combine only when the things they count are disjoint. The reason the original page was right not to add its two floors is that they both counted the same comparisons. The reason this page may add its two is a sentence about the structure of the partial order: a non-output cannot lie between two outputs. That sentence is where the whole improvement lives, and it is not about counting at all.

That is the same discipline the count is not the time applies to a measurement rather than to a bound: a number is trustworthy only alongside a statement of what it is a number of, and a floor’s statement is the argument that produced it.

The floor moves when the question does made the general point that a bound belongs to a question. This adds the finer one: a bound also belongs to an argument, and a question can have several arguments whose combination is a better bound than any of them, when their charges fall on different objects.

What is not measured here #

One method against the floors. The tournament is the one the ratios are drawn for, because it is the method the earlier page found closest. The other five are on the reproduced plate and are not recomputed against the new floor point by point.

Nothing here is about the average. Both floors bound the worst case. A method could beat either of them on most inputs and pay on one, and a distribution computed rather than sampled is the page that measures what a distribution of counts looks like when the worst case is not the whole story. The tournament happens to be the wrong method to raise that objection about, since its count is nearly the same on every input.

A bound, not an algorithm. The floor says no method goes under 103,636 at the crossing and says nothing about how a method might reach it. How close anything gets to the floor is the standing measurement of that gap, and this page narrows one entry in it without closing it.

Distinct keys. The chain argument uses “anything smaller than an output is an output”, which needs no two keys equal. With ties the outputs are a multiset and the argument needs restating; the floor when the values repeat is what happens to the information floor in that case and the same care would be needed here.

Worst case, not expected. Everything here is a worst-case bound against an adversary, and the tournament’s measured counts are on one random arrangement. The two are comparable only because the tournament’s count barely depends on its input — the count of the part that was read measured it moving by thirteen comparisons across sorted, random and reversed input.

Exact only to six elements. The minimax is a search over sets of orderings and costs 127,743 states at six elements; seven would be several hundred times that, since the states are subsets of a set that itself grows by a factor of seven. The slack of one or two comparisons is what can be seen, and two points are not a measurement of how it grows.

No account of where the slack sits. At $n = 6$, $k = 2$ the floor demands 5 and the truth is 7, and nothing here says what the missing two comparisons are doing. The last section proposes the obvious candidate and does not measure it.

And the floor is not claimed to be the best known. The literature on selection has sharper bounds for particular $k$, and for $k = 2$ the exact answer $n - 2 + \lceil \log_2 n \rceil$ beats this floor by $\lceil \log_2 n \rceil - 1$. What is claimed is that this one is provable in a paragraph, computable at every $k$, and enough to attribute the peak.

Still open: the third kind of comparison #

The argument divides comparisons by their loser: a non-output loses, or an output loses. It then charges the first set for elimination and the second for ordering, and stops.

There is a third thing a comparison can do that neither charge counts. A comparison between two non-outputs eliminates one of them and also tells the algorithm something about the other, and a comparison in which an output beats a non-output identifies part of the boundary between the two groups — which is work the algorithm must do, since it has to know which $k$ elements are smallest, and neither term above pays for it.

The measurement that follows asks what that boundary costs. It counts, in an optimal decision tree at sizes where one can be computed, how many comparisons have a non-output as their loser beyond the $n - k$ the first term demands, and whether that excess tracks $\lceil \log_2 \binom{n}{k} \rceil$ — the bits needed to name the set — or something smaller. If it tracks the set’s own information content, the floor becomes three terms rather than two, and the slack at $n = 6$, $k = 2$ has an explanation rather than a size.