The comparisons that name the answer

Two floors that can be added found a floor under returning the $k$ smallest of $n$ keys in order by splitting comparisons according to their loser. At least $n - k$ comparisons must have a key that is not returned as their loser, since every such key has to lose once. At least $\lceil \log_2 k! \rceil$ must have a returned key as their loser, because the returned keys have to be put in order and only comparisons among them can do that. The two sets are disjoint, so the charges add. At $n = 65{,}536$ and $k = 4{,}000$ that floor was 103,636, against a knockout tournament’s 125,388.

It ended by naming what the two charges leave out. An algorithm has to know which $k$ keys are smallest, not just order some keys and eliminate others. A comparison between a returned key and one that is not returned establishes part of that boundary. Neither charge pays for it.

That boundary has a price, it can be written down, and at the sizes where the exact optimum can be solved it accounts for almost the whole gap.

The third charge #

A way of seeing the cost is to hand the answer back one key at a time. Naming the smallest key means choosing it from $n$. Naming the second means choosing it from the remaining $n - 1$, and so on down to the $(k-1)$-th output, chosen from $n - k + 2$. Picking those out in order distinguishes $n(n-1)\cdots(n-k+2) = n!/(n-k+1)!$ possibilities, so it costs at least $\log_2$ of that many comparisons. What remains is to find the $k$-th output. That is the minimum of the $n - k + 1$ keys not yet named, and finding a minimum of $n - k + 1$ keys takes $n - k$ comparisons, each losing a key that is not returned.

Put together:

$$n - k + \left\lceil \log_2 \frac{n!}{(n-k+1)!} \right\rceil$$

The argument above is a way to see the shape and not a proof, because it assumes the algorithm works in the order the answer is described. A proof has to show that no algorithm can share comparisons between the two parts, and a bound of exactly this form is established for selection problems in the literature, by Fussenegger and Gabow. The measurement below is a check that does not depend on either the sketch or the citation. It solves the problem exactly where it can be solved, and it checks whether the bound is ever violated or loose.

At the two ends the bound is exactly what it should be. At $k = 1$ the logarithm is of $1$ and the floor is $n - 1$, the known cost of a minimum. At $k = n$ it is $\log_2 n!$, the sorting floor. In between it is larger than the earlier two-part floor. That floor charged $\log_2 k!$ for putting the outputs in order, and this one charges $\log_2 n!/(n-k+1)!$ for naming all but one of them in order, which is more whenever $k$ is less than $n$.

Naming the set, less a little #

Two floors that can be added asked a specific question about the missing charge: does the boundary cost track $\lceil \log_2 \binom{n}{k} \rceil$, the bits needed to name the set of returned keys, or something smaller? The new floor answers it by arithmetic.

What the new floor adds to the old one is the difference between naming $k - 1$ outputs in order and ordering $k$ outputs:

$$\log_2 \frac{n!}{(n-k+1)!} - \log_2 k! \;=\; \log_2 \binom{n}{k} - \log_2 \frac{n-k+1}{k}.$$

So the boundary costs the bits that name the set, less $\log_2$ of the ratio of keys not returned to keys returned. At $n = 65{,}536$ and $k = 4{,}000$, naming the set is 21,720.6 bits and the naming charge is 21,704.7, sixteen bits less. At $k = 16{,}000$ the two are 52,542.5 and 52,526.9. At six keys and $k = 2$ they are 3.9 and 1.6. The answer to the earlier question is that the boundary tracks the set’s information content almost exactly, and the few bits by which it falls short are the elimination work that also tells the algorithm something about the boundary. Each of the $n - k$ losing comparisons tells an algorithm that its loser is not returned, and that is part of naming the set. The formula credits that overlap once, as a logarithm, and no more.

This is the adversary’s view of the same charge, the one the adversary who hides the edge described for connectivity. An adversary answering an algorithm that wants the $k$ smallest keeps as many possible sets alive as it can. Each comparison can at most halve them, whatever the comparison is also doing, so an algorithm must ask enough questions to cut $\binom{n}{k}$ sets down to one. The earlier floor counted comparisons by their losers and never counted sets, which is why it missed this.

Solved exactly up to six keys #

The exact optimum for returning the $k$ smallest in order comes from the same kind of game the floor a merge cannot reach solved for merging. A state of knowledge is the transitive closure of the comparisons made so far, stored as one bitmask per key of the keys known to be smaller. The answer is settled when $k$ keys form a chain, the $j$-th with exactly $j - 1$ keys known below it, and every other key is known to be above the whole chain. There are 4,231 such partial orders on five labelled keys and 130,023 on six, and the solve visits all of them. At four keys and below it agrees with an older solver that works on sets of permutations and shares no representation with it.

The three cells where the naming floor lifts the earlier one to the optimum are the cells that essay could not explain. At six keys and $k = 2$ the earlier floor said five and the optimum is seven. The naming floor says seven exactly: four comparisons to eliminate, plus $\lceil \log_2 6 \rceil = 3$ to name the smallest. The earlier floor charged $\lceil \log_2 2! \rceil = 1$ for putting two keys in order and nothing for knowing that those two were the right two. Knowing that is worth two further comparisons at six keys, and at 65,536 keys it is worth tens of thousands.

The naming floor is never above the optimum, in any of the eighteen cases. A floor that exceeded the optimum anywhere would be refuted, and none of the eighteen cases does. It is also not always exact. At six keys with $k = 3$ or $4$ the optimum is one higher. So a gap remains, it is at most one comparison at these sizes, and the naming floor does not explain it. The cells it lifts are the ones where the earlier floor was weakest, middle values of $k$ on the larger sizes.

What the parts are worth at scale #

At a few keys the three charges are a few comparisons each. At 65,536 keys they are not, and their proportions change with $k$.

At $k = 4{,}000$ the naming charge is 21,705 comparisons, a sixth of the floor and within 47 of the whole gap between the old floor and the tournament. Adding it moves the floor to within 47 comparisons of what the tournament made on this input. Two floors that can be added said that at most seventeen per cent of the tournament’s work at this point could be removed by any method, and quite possibly none of it. The new floor shrinks the first figure to at most 0.04%. That is still a comparison between a worst-case floor and one input’s count, and it is the part of this that needs saying carefully.

At $k = 16{,}000$ ordering dominates, since $\log_2 16{,}000!$ is two hundred thousand comparisons. The naming charge has grown to 52,527 but is a smaller share, about one sixth again. Elimination has fallen to 49,536 because fewer keys are thrown away. The earlier floor is 17% short of the new one here, as it was at $k = 4{,}000$, and the tournament’s distance to the new floor has grown to 804 comparisons, 0.27%.

Set side by side, the three parts describe how the problem changes as $k$ grows. At $k = 10$ the floor is 65,670 comparisons: 65,526 to eliminate, 22 to order ten keys and 122 more to name them. Almost everything is elimination, and the problem is essentially finding a minimum. At $k = 4{,}000$ elimination is 49% of the floor, ordering 34% and naming 17%. At $k = 16{,}000$ ordering has taken over at 66%, elimination is down to 16% and naming stays at 17%. Near $k = n$ the problem is a sort and the floor is the sorting floor.

Naming holds a roughly constant share across the middle of the range, and that is the part that explains the earlier floor’s pattern. That floor was missing a sixth of the true floor across a wide band of $k$, and its ratio to the tournament rose with $k$ and then fell at the ends. The shape came from the share of a charge it was not making, not from any feature of the tournament.

The tournament against the new floor #

The whole sweep shows how close the tournament stays and where it starts to pull away.

For $k = 1, 2, 10, 40$ and $100$, the tournament’s count on this input equals the naming floor exactly. At $k = 400$ it is one above, at $1{,}000$ three above, at $4{,}000$ forty-seven above. The distance only becomes visible past $k = 16{,}000$. At $k = n$ the tournament has become merge sort, as the count of the part that was read found, and its 965,656 comparisons are 1.2% above the sorting floor.

The formula shows why the two agree for small $k$. A tournament finds the minimum in $n - 1$ comparisons, which is the elimination charge and the first naming step together. Each later output costs one replay down the tree, about $\log_2 n$ comparisons. The naming charge for the $j$-th output is $\log_2(n - j + 1)$ bits, which for small $j$ is only a hair under $\log_2 n$, so each replay pays almost exactly its naming charge. As $j$ grows the charge falls further below $\log_2 n$ while the replay does not shrink with it, and the excess accumulates. Which replays contribute each extra comparison is not traced here.

Against the new floor, the other methods’ distances become meaningful too. Building a heap and popping $k$ times sits near 1.9 at every $k$. Heap construction and the first pop cost about $1.88\,n$ comparisons where the floor needs $n - 1$, and each further pop costs about $2 \log_2 n$, thirty comparisons, where naming needs about sixteen. Neither ratio depends much on $k$, and the plate is flat. Selecting and then sorting is about twice the floor at small $k$, because a randomised selection spends roughly two comparisons per key to find the boundary, averaged over the eight seeds. It approaches the floor as $k$ grows and sorting dominates, reaching 1.10 at $k = n$, which is the sort’s own distance to $\log_2 n!$.

Against the larger of the two original floors the tournament was 1.97 at $k = 4{,}000$, and against their sum it was 1.21. Against a floor that charges for naming the answer, the tournament is essentially optimal at every $k$ below a quarter of $n$, and the heap is almost twice the floor everywhere.

Where the floor leaves room for design #

A floor that is nearly met changes what a design question means. For the tournament at small $k$ nothing is left to improve in the comparison count, so improvements have to come from somewhere else. One run, four counts, four answers is the reminder that comparisons are one count among several. A tournament stores a tree of $2n$ entries and moves keys through it on every replay, while building a heap is done in place. The heap pays roughly twice the floor in comparisons and nothing in extra space, the tournament pays the floor in comparisons and a tree in space, and which one wins depends on how the costs are weighted.

What the floor does rule out is a cleverer comparison strategy for small $k$. Before it, the earlier floor left a fifth of the tournament’s work unexplained at $k = 4{,}000$, and a reader could reasonably have looked for a method that saved it. After it, the unexplained part is 47 comparisons in 125,388, and a search for a better method at that size is a search for less than a tenth of a per cent. The floor under every comparison sort did the same service for sorting, closing merge sort’s gap to within a couple of per cent. Closing a gap like this does more for a design question than any single measurement of a method can.

What the floor settles, and what the comparison does not #

The floor is a worst-case statement. No algorithm returns the $k$ smallest in order on every input in fewer comparisons than it states. The tournament’s count is from one shuffled input. So “the tournament equals the floor at $k = 100$” means that on this input it used exactly the number of comparisons no algorithm can beat on its worst input. It does not say the tournament’s own worst case equals the floor. A tournament’s cost depends on the input only through the replay paths, which are nearly fixed by the tree’s shape. Its worst case is therefore unlikely to be far above this count, but nothing here measures it.

Settled, by exact solve: at every size from three to six keys and every $k$, the naming floor is at most the optimum and at least the earlier floor, and it equals the optimum in 16 of 18 cases against the earlier floor’s 13. At four keys and below two independent solvers agree.

Settled, by arithmetic: at 65,536 keys the naming charge adds 21,705 comparisons at $k = 4{,}000$ and 52,527 at $k = 16{,}000$. It adds nothing at $k = 1$ or $k = n$.

Not settled:

The two cases at six keys. The optimum exceeds the naming floor by one at $k = 3$ and $k = 4$. A fourth charge might explain them, or they might be the kind of gap that the floor a merge cannot reach found for merging, where no single comparison divides the remaining possibilities evenly enough and the ceiling rounds against the algorithm. Seven keys, with 6,129,859 partial orders, is where that would show, and it is beyond what is solved here.

The tournament’s worst case. One input was measured. The claim that no other method can save more than 0.04% at $k = 4{,}000$ holds only for methods measured on inputs no easier than this one.

Still open: the tournament’s own worst case #

The tournament’s excess over the naming floor has a candidate source: the tree keeps its original depth while the keys it still holds shrink, so each late replay pays for levels that no longer carry a full bit. If that is the source, the excess should depend on where $n - k$ sits relative to powers of two, and a tournament that rebuilt its tree whenever the remaining keys halved should remove most of it, at the cost of the rebuild.

The measurement that follows computes the tournament’s worst case exactly at small $n$ with the same partial-order solve, restricted to the tournament’s own sequence of questions. At large $n$ it searches for bad inputs by the hill-climbing the worst case found by climbing used for sorts. Then it builds the rebuilding variant and compares both against the naming floor at every $k$. The prediction is that the ordinary tournament’s worst case lies within one comparison per output of the floor, and that the rebuilding variant is exact until $k$ passes half of $n$. If both hold, the gap left by the floor at large $k$ is a property of one algorithm’s tree, not of the problem.