The floor moves when the question does

The decision-tree argument that gives sorting its floor is not really about sorting. It is about how much a yes-or-no question can convey, and it applies to any problem where the algorithm learns by asking them.

Change the problem and the same machinery gives a different number. The machinery is: count the outcomes the algorithm must be able to distinguish, take the base-two logarithm, and that is how many comparisons it needs at minimum.

Applied to two questions about the same 4,096 elements:

• Sort them. There are $4096!$ possible orderings. $\log_2(4096!) = 43{,}250$ comparisons.
• Find one of them, given that they are sorted. There are 4,097 possible answers — each position, plus “absent”. $\lceil \log_2 4097 \rceil = 13$ comparisons, because $2^{12} = 4096$ is one short.

A factor of about 3,300, from the same argument applied to the same data. The difference is entirely in how many answers the algorithm must be able to produce.

Binary search is optimal, not merely good #

The searching bound is worth dwelling on because it is one of the few places in this subject where an algorithm meets its lower bound exactly, with nothing left over.

The argument is the same as for sorting. A search on a sorted array of $n$ elements must distinguish $n + 1$ outcomes: the target is at position 0, or 1, …, or $n-1$, or is not present. Each comparison yields one bit. A binary tree distinguishing $n+1$ outcomes has depth at least $\lceil \log_2(n+1) \rceil$, so some target costs at least that many comparisons.

For $n = 4096$: $\lceil \log_2 4097 \rceil = 13$, since $2^{12} = 4096$ falls one outcome short.

Measured over all 4,096 possible targets, binary search’s worst case is exactly 13. Not 14, not 13.4 — thirteen, matching the floor with no slack at all. The site’s gate asserts this equality rather than an inequality, because “binary search is optimal” is a stronger and more interesting claim than “binary search is efficient”, and equality is the form the stronger claim takes.

The reason it achieves the bound is visible in the algorithm. Each comparison splits the remaining candidate range as close to in half as possible, so each one extracts a full bit. There is no navigation overhead, no repeated work, nothing discarded. Merge sort comes within 2.2% of its floor and the 2.2% is structural; binary search has no gap to explain.

Why the sorting floor is so much higher #

The factor of 3,300 is not because sorting is “harder” in some vague sense. It is arithmetic.

Sorting must distinguish $n!$ outcomes and searching must distinguish $n+1$. By Stirling, $\log_2(n!) \approx n \log_2 n - 1.44n$, which grows almost linearly in $n$, while $\log_2(n+1)$ grows logarithmically. The gap therefore widens without limit: at $n = 16$ it is a factor of 9, at $n = 4{,}096$ a factor of 3,300, and at a million a factor of about a million.

The useful way to hold this is in bits. Sorting a million elements requires learning about 18.5 million bits of information about the input. Finding one element among a million sorted ones requires learning 20. It is not surprising that one takes longer.

This also explains something that surprises people the first time they meet it: it is worth sorting an array before searching it only if it is going to be searched many times. One search costs 20 comparisons on a sorted million-element array and about 500,000 on an unsorted one. Sorting costs 18.5 million. The sort pays for itself after roughly thirty-seven searches, and not before.

Where the bound stops applying #

The theorem is about algorithms that learn through comparisons. Step outside that class and the floor does not apply — not because the argument is wrong, but because its premise is false.

Counting sort. Given $n$ integers known to lie in $[0, r)$, allocate $r$ counters, walk the input incrementing them, then walk the counters emitting values. Zero comparisons. $\Theta(n + r)$ operations. On a million integers in the range 0–255 this is dramatically faster than any comparison sort, and it does not contradict the floor because it never compares anything.

What it does instead is use each element’s value as an address. That operation is not in the decision-tree model. It is also not free in practice: the counter array must fit in memory, so counting sort demands a bounded key range, and its memory access pattern is a scatter rather than a sweep, which real hardware charges for.

Interpolation search. On uniformly distributed sorted data, guessing where the target should be — rather than always splitting in the middle — reaches $O(\log \log n)$ expected comparisons. That is below the $\log_2(n+1)$ floor, and again it does not contradict it: the floor is a worst-case bound over all inputs, and interpolation search’s worst case is $\Theta(n)$ when the data is distributed badly. The average improves; the guarantee does not.

Both cases show the same thing. A lower bound comes with a model of computation attached, and the model is doing as much work as the mathematics — in the same way that a complexity class comes with an input distribution attached and means very little without one. Quoting a bound without its model is quoting half of it.

Linear search is not stupid #

Linear search’s worst case is $n$ comparisons — 4,096 where binary search needs 13 — and by the comparison count it is one of the worst algorithms on this site.

It is also the algorithm most likely to win on a small array, and the reason is not about comparisons at all.

Linear search reads memory in perfect sequential order. Every access is to the next element, which is the one pattern hardware is unambiguously good at: the prefetcher sees the stream and fetches ahead, and a cache line holding eight elements is paid for once and used eight times. Binary search jumps: first to the middle, then to a quarter point, then an eighth. Every one of the first several probes is to a location far from the last, and on a large array each is a fresh cache miss.

So the comparison ratio is 315 to 1 in binary search’s favour at $n = 4096$, and the cache-miss ratio is closer to 1 to 1 — binary search’s thirteen probes are thirteen misses, while linear search’s 4,096 accesses are 512 misses and every one of them prefetchable. On small arrays, where the whole thing fits in cache anyway, linear search’s freedom from index arithmetic and unpredictable branches makes it genuinely faster, and this is why real implementations of things like std::lower_bound fall back to linear scanning below a threshold.

The floor is about comparisons. It is silent about everything that decides which algorithm is actually worth writing, which is the machine field’s entire subject.

A third question, for scale #

There is a question between the two, and it makes the pattern clearer.

Find the smallest element in an unsorted array of $n$. There are $n$ possible answers, so the information-theoretic floor is $\log_2 n$ — exactly 12 for $n = 4096$.

But the achievable bound is $n - 1$, not 12, and the difference is instructive. The information-theoretic argument gives a necessary condition and not a sufficient one. To be sure that element $x$ is the minimum, every other element must have lost a comparison at some point — otherwise it might be smaller and nobody checked. That is $n-1$ distinct losses, each requiring its own comparison, so $n-1$ comparisons are needed.

The counting argument gives 12 and the correct answer is 4,095. The bound is valid and enormously loose, which is the normal situation for lower bounds and the reason sorting’s floor is unusual. Sorting happens to be a problem where the information-theoretic bound is also achievable to within a couple of percent. Most problems are not like that, and the gap between what is provably necessary and what is achievably sufficient is where most of the open questions in the subject live.

Finding both the minimum and the maximum is a small further case worth knowing: the naive method costs $2n - 2$ comparisons, and processing elements in pairs — compare the pair to each other first, then the smaller against the running minimum and the larger against the running maximum — costs $\lceil 3n/2 \rceil - 2$. That saving of 25% is provably optimal, and it is exactly the kind of constant-factor result that a complexity class cannot express, since both methods are $\Theta(n)$ — and exactly the kind that measurement is good at.

Reading a floor as a budget #

There is a way of using these numbers that has nothing to do with proving anything, and it is the one most likely to be useful in practice.

A floor converts into a time budget the moment the cost of one comparison is known.

Sorting a million strings by a locale-aware collation: the floor is 18.5 million comparisons. If a collation comparison takes 200 nanoseconds — which is realistic for anything doing Unicode normalisation — then no comparison sort finishes this in under 3.7 seconds, on any hardware, with any amount of parallelism per comparison. If the requirement is one second, the requirement cannot be met by sorting with comparisons, and the conversation has to move to precomputing sort keys or to a radix method.

That is a genuinely useful thing to be able to say early in a design discussion, and it takes one logarithm to say it. The equivalent statement from a complexity class — “sorting is $\Theta(n \log n)$” — supports no such calculation, because it has no constant in it.

The same arithmetic in the other direction is what makes binary search’s optimality worth knowing. Thirteen comparisons on 4,096 elements is not going to be beaten, so where a lookup is too slow the problem is not the search algorithm. It is the memory access pattern, or the comparison cost, or the fact that the lookup is happening at all.

The gap, at four sizes #

The two floors are both exact and they diverge, so the interesting quantity is not either of them but the ratio — and a ratio is a claim about a sweep.

Doubling the array roughly doubles the first floor and adds one to the second, so the gap widens by a factor of about two per doubling. Two more points make that visible rather than asserted.

The bound for a related question, and why it is different #

One more variation makes the pattern complete, and it is the one people most often expect to be free.

Find the median of $n$ unsorted elements. There are $n$ possible answers, so the counting argument gives $\log_2 n$ — 12 for $n = 4096$, and useless, as it was for the minimum. The achievable bound is linear: median-of-medians selects in $\Theta(n)$ comparisons in the worst case, with a constant that is large but bounded.

That is a genuinely surprising result the first time one meets it, because the obvious way to find the median is to sort, which costs $n \log n$. Selection is strictly easier than sorting — it needs less information, since the ranks of the elements that are not the median do not have to be determined — and the gap between $\Theta(n)$ and $\Theta(n \log n)$ is exactly what that lesser information is worth.

So three questions about the same array give three floors and three achievable bounds:

Only the third has a tight information-theoretic floor. Sorting’s is tight for a different reason — the achievable happens to match — and selection’s is not tight at all, with the real bound coming from an argument about how many elements must be touched rather than about how many bits are needed.

Two questions asked together are not two questions #

There is one more way the floor moves, and it is the least intuitive: asking two questions at once can be cheaper than asking each of them separately.

Finding the minimum of $n$ values takes exactly $n-1$ comparisons and no fewer. The argument is a tournament: every element except the answer must lose at least one comparison, each comparison produces one loser, so $n-1$ comparisons are needed and a single sweep achieves it. Finding the maximum is the same bound by symmetry.

Two questions, each with a floor of $n-1$. The obvious conclusion is that asking both costs $2n-2$, and a single sweep that tracks both does exactly that. Measured on 1,024 values, it spends 2,046 comparisons — the arithmetic, on the nose.

The floor for the pair is not $2n-2$. It is $\lceil 3n/2 \rceil - 2$, and the algorithm that reaches it takes the elements two at a time: compare the pair with each other first, then send only the smaller one to the running minimum and only the larger to the running maximum. Three comparisons per two elements instead of four. On the same 1,024 values it spends 1,534 comparisons, which is $\lceil 3 \cdot 1024/2\rceil - 2$ exactly.

A quarter of the work in the naive version was wasted, and it was wasted on comparisons whose answers were already implied. An element that lost to its partner cannot be the maximum; asking whether it beats the running maximum is asking something already known.

So floors are not additive. Two questions asked together are one question, with its own floor, and that floor can be strictly below the sum. This is the same lesson as the sorting bound arriving from the other side: the floor belongs to the question, and combining two questions produces a new one rather than a total.

Two kinds of floor, and which one binds #

The table of three questions has a pattern in it that is worth extracting, because it says in advance whether a counting argument will be worth computing.

Line up the ratios of achievable to counting bound. Searching a sorted array: 13 against 13, a ratio of 1.00. Sorting: about 44,000 against 43,250, a ratio of 1.02. Finding the minimum: 4,095 against 12, a ratio of 341. Finding the minimum and maximum together: 1,534 against $\log_2(n(n-1)) \approx 20$, a ratio of 77.

Two of those are tight to a rounding and two are useless, and the split is not by the size of the answer — searching has a twelve-bit answer and is exactly tight, minimum-finding has a twelve-bit answer and is off by a factor of three hundred.

The distinction is what kind of argument produces the real bound.

A bisection bound counts outcomes and divides by the bit a comparison yields. It binds when every comparison can be arranged to halve the remaining possibilities, which requires that no individual element needs attention of its own. Searching a sorted array is the pure case: the sortedness is a promise carried by the input, so a probe in the middle genuinely eliminates half the array without anything else being examined.

A covering bound counts what must be certified. Finding the minimum needs every other element to have lost a comparison — $n-1$ distinct losses, one per element, no two shareable — and that requirement has nothing to do with information at all. It is a statement that certain data cannot go unexamined.

The larger of the two binds, and which is larger is decided by whether the input carries a promise. Given sortedness, nothing needs individual attention and the bisection bound is the whole story. Given nothing, every element needs its own certificate and the covering bound is the whole story. Sorting is the odd case where the output is large enough that the bisection bound overtakes the covering one — $n\log_2 n$ against the $n-1$ that a covering argument would give — which is exactly why sorting is the problem where a counting argument is famous.

That is a rule worth having before doing the arithmetic. Compute a counting bound when the answer is large or the input is promised, and expect it to be useless otherwise. The minimum, the median and the mode all have small answers and unpromised inputs, and for all three the counting bound is a number in the tens against an achievable in the thousands.

It also names what the min-and-max result actually is. $\lceil 3n/2\rceil - 2$ is a covering bound with the certificates shared: an element that loses to its partner is certified as not-the-maximum by that one comparison, so a single comparison discharges two obligations. The saving of a quarter is exactly the fraction of certificates that can be doubled up, and no bisection argument is involved anywhere.

The adversary who hides the edge is a covering bound in its purest form — every edge must be read, because an unread one could be the one that matters — and how close anything gets to the floor is the measurement that only means something when the floor is the binding one.

What a lower bound is for #

It says where not to look.

Where the cost is comparisons and the task is sorting, merge sort is within 2.2% of optimal and there is nothing worth finding. Where the task is searching a sorted array, binary search is exactly optimal and there is nothing at all. Those are unusual and valuable pieces of information, they are the reason to compute a floor even with no intention of writing a new algorithm, and they are what turns a distance-to-floor ratio into advice rather than trivia.

They also indicate what to change when more is needed. Where sorting is too slow and merge sort is already near the floor, the answer is not a better comparison sort — it is to stop comparing. Counting sort, radix sort and bucket sort exist because somebody noticed that the wall was a property of the question, and asked a different one.