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 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.

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.