Comparison Lower Bounds From Decision Trees and Adversaries

An upper bound comes with a witness: the algorithm that achieves it. A lower bound is a statement about every algorithm in a class, and it has to hold for methods nobody has written yet. The two standard techniques for such statements are counting the outcomes an algorithm must distinguish and constructing an adversary that answers each query so as to delay the conclusion. Both are proofs about a restricted model, and the restriction is doing real work in each of them.

The decision tree as a model of the algorithm

Fix a class of algorithms whose only operation on the input is a comparison, and whose behaviour therefore depends solely on the outcomes of those comparisons. Any such algorithm can be unfolded into a decision tree. Internal nodes are comparisons, and each child corresponds to one of the possible outcomes. A leaf is reached after a specific sequence of outcomes, and the algorithm, having no other information, must behave identically for every input that leads to that leaf. Two requirements follow immediately.

First, every input that demands a distinct output must reach a distinct leaf, so the number of leaves is at least the number of distinguishable outcomes. Second, a binary tree of height h has at most 2^h leaves, since each level can at most double the leaf count. Combining them gives the information-theoretic bound

h ≥ log₂ N

where N is the number of distinct outputs the algorithm must be able to produce. This argument never mentions the algorithm’s strategy, which is the point: it holds for every comparison-based method at once.

The bound is about comparisons only. Comparisons of integers, strings, and floating-point values are all the same query to this model, and an algorithm that reads the input without comparing it is outside the model entirely.

Sorting: n! leaves and the n log n bound

Sorting n distinct keys decides which of the n! permutations is the sorted order, so N = n! and any comparison sort needs at least log₂(n!) comparisons in the worst case. A crude bound uses only the largest half of the factorial:

n! ≥ (n/2)^(n/2)  →  log₂(n!) ≥ (n/2)·log₂(n/2)

which is Ω(n log n). The sharper form, from Stirling’s approximation, is

log₂(n!) = n·log₂ n − n·log₂ e + ½·log₂(2πn) + O(1/n)

with log₂ e ≈ 1.4427. At n = 10⁶ the first term is about 1.99 × 10⁷, the second subtracts about 1.44 × 10⁶, and the result is roughly 1.85 × 10⁷ bits of information that the sequence of comparison outcomes must carry. The linear term is not negligible: it is about 7 percent of the leading term at that size.

Merging illustrates why the lower bound is tight in a natural way. Merging two sorted runs of n/2 elements each has C(n, n/2) possible outcomes, and log₂ C(n, n/2) ≈ n − ½·log₂(πn/2), so the n − 1 comparisons that the standard merge performs are within a logarithmic term of optimal. The remaining gap is genuinely unclosable in the model: no merge algorithm performs fewer than n − 1 comparisons in the worst case, so the counting bound is off by the logarithm and nothing more.

import math

def comparisons_lower_bound(n):
    """Bits of information in a permutation: ceil(log2(n!)) without overflow."""
    return math.ceil(math.lgamma(n + 1) / math.log(2))

for n in (8, 64, 1024, 10 ** 6):
    print(n, comparisons_lower_bound(n))

The lgamma form avoids building the factorial itself, so the bound can be evaluated for inputs where n! has more digits than the machine has words.

Widening the query does not help. If each node of the tree compares k keys at once and branches k+1 ways, the leaf count per level grows by a factor k+1 while each query costs at least log k times a single comparison, so the product of query count and query cost stays Ω(n log n). This is the standard reason comparison sorts cannot escape the bound by comparing more elements at a time.

Adversary arguments when counting is not enough

Counting outcomes proves a bound on the number of queries but says nothing about which ones are wasted. An adversary argument answers a query so as to leave as many consistent inputs as possible, and then shows that the algorithm needs many queries before only one input is left.

Finding the maximum of n elements needs n − 1 comparisons. Every element except the maximum must lose at least one comparison, because an element that has never lost is still a candidate for the maximum, and the algorithm cannot distinguish the input in which it is the maximum from one in which it is not. The adversary answers every comparison so that the element that has lost fewer times loses, which keeps the number of candidates at n − 1 after the first comparison and decrements it by exactly one per subsequent comparison.

Finding the minimum and the maximum together takes at least ⌈3n/2⌉ − 2 comparisons, so for n = 10 the bound is 13. Every element must accumulate two facts: at least one loss to be excluded from being the maximum, and at least one win to be excluded from being the minimum. A comparison produces one win and one loss, so it distributes exactly two of the needed marks, and 2n marks are needed in total. The − 2 comes from the final maximum and minimum, which need only the marks that exclude them from the other role. The matching algorithm achieves the bound: pair up elements with ⌈n/2⌉ comparisons, then scan the winners for the maximum and the losers for the minimum in ⌈n/2⌉ − 1 comparisons each, using the ordering inside each pair so that the pairing comparisons do double duty.

Selection has a lower bound of the same character that resists matching. Finding the median requires at least 2n comparisons, and no comparison-based algorithm is known to reach that barrier; the best published upper bounds remain a constant factor above it. The gap between the two is not a proof of slack in the model but a statement about the difficulty of the exact constant.

Where the model stops applying

Three escapes from the comparison model are routine, and each one changes the problem rather than the algorithm.

Hashing answers membership questions without comparing keys at all, computing an address from the key’s bits. The Ω(n log n) bound does not apply because the model changed: the algorithm uses arithmetic on the key, not an oracle returning the order of two elements. The cost reappears as the assumption that such an address function exists, and the analysis of what a fixed function can be forced to do is covered by expected and amortized cost.

Radix sorting reads key digits and never compares two full keys, so it sorts n keys of b bits in Θ((b/r)(n + 2^r)) operations, which is linear in n for fixed key width. The bound and the comparison bound are not in conflict because they count different operations.

Algebraic decision trees replace comparisons with tests of the sign of a polynomial in the input coordinates. Ben-Or’s theorem gives a lower bound in that model based on the number of connected components of the set of inputs that must be accepted, and it yields Ω(n log n) for element distinctness and for the decision problem behind sorting. The model is strictly stronger than the comparison model, so the bound is correspondingly stronger evidence, and for linear decision trees, whose tests are signs of linear functions, the element-distinctness bound is proved by a separate argument.

Reading the bound as an engineering number

The value of log₂(n!) is the number of bits a comparison sort must extract. Measured against the leading term, the deficit at n = 10⁶ is about 7 percent, and at n = 1024 the bound is about 8,770 comparisons against a leading term of 10,240. Implementation effort spent shaving comparisons below that floor is wasted; effort spent reducing the cost of each comparison is not, which is why cache locality and branch prediction, rather than comparison counting, dominate the performance of a real sort. The choice of what a comparison costs in a given machine model is treated in the word-RAM cost model.