Cairn
guides · reference tool, not a category comparison

↩ back to Guides

Lower Bounds: Proving You Can't Do Better

Every Complexity section on this site states an upper bound — this algorithm costs at most this much. A lower bound is the opposite kind of claim, and a stronger one: not "here's one way to do it," but "no way exists, now or ever, that does better" — within a clearly stated model of what the algorithm is allowed to do. Counting Sort's own Pitfalls section already leans on one, asserting that "any sort that only asks 'is A bigger than B?' needs at least Ω(n log n) comparisons" without ever deriving it. This page derives that bound, plus two more already touched elsewhere on the site — Linear Search's own Complexity section states a matching Ω(n) directly; Binary Search's own page proves only the upper half — using the two techniques that cover nearly every lower bound a working programmer runs into: the decision-tree argument and the adversary argument.

Try it: measure the gap

Pick a size n. The table below computes, for that exact n: the proven minimum number of comparisons any correct comparison-based sort must make in the worst case (derived in the next section), against the real worst-case comparison counts of sorts already on this site — Merge Sort's exact recursive worst-case formula, and Selection Sort's / Insertion Sort's shared n(n-1)/2.

The decision-tree argument

Model any comparison-based sorting algorithm as a binary tree: each internal node is one comparison between two elements, its two children are the two possible outcomes, and each leaf is the one fixed output ordering the algorithm commits to once it reaches that leaf. For the algorithm to be correct on every input, every one of the n! possible orderings of n distinct elements has to reach a different leaf — if two different true orderings landed on the same leaf, the algorithm would hand back the identical rearrangement for two genuinely different inputs, which is simply wrong for one of them. A binary tree of height h has at most 2h leaves, so a tree with at least n! leaves needs h ≥ log₂(n!). The algorithm's worst-case comparison count is exactly the height of whichever branch some input forces it down, so no comparison-based sort can guarantee fewer than ⌈log₂(n!)⌉ comparisons — and Stirling's approximation turns that into the familiar Ω(n log n): log₂(n!) = n log₂ n − n log₂ e + Θ(log n), an n log n term with nothing smaller able to catch up to it.

Small enough to draw by hand at n = 3: three elements have 3! = 6 possible orders, so any correct tree needs height at least ⌈log₂ 6⌉ = 3. One tree that hits that minimum exactly (there are others — this one happens to match Insertion Sort's own comparison sequence on three elements a, b, c):

All six permutations of three elements appear exactly once, as they must for the algorithm to be correct — two comparisons on the two orders that happen to need no third check, three on the other four, never fewer than the 3 the argument above demands and never needing a fourth.

Searching inherits the same argument

Binary Search's own Complexity section proves an O(log n) upper bound without ever asking whether a faster comparison-based search could exist. The same leaf-counting argument answers that too, just with a different leaf count. Searching a sorted array of n distinct elements for a target has to distinguish among 2n + 1 possible outcomes: the target matches one of the n elements exactly, or it falls into one of the n + 1 gaps around and between them (before the first, between any adjacent pair, or after the last) — and every one of those 2n + 1 cases needs its own leaf, for the identical reason as above: collapse two of them onto one leaf and the algorithm answers wrong for at least one. Allowing three-way comparisons (<, =, >) rather than Binary Search's own two-way <= gives each internal node up to three children instead of two, so the bound becomes h ≥ log₃(2n + 1) — still Ω(log n), and Binary Search's real comparison count sits within a constant factor of it (one three-way question is worth at most log₂3 ≈ 1.585 two-way questions, the exact same log₂3 that shows up as Karatsuba Multiplication's recursion exponent on the Master Theorem page — unrelated problems, same number, for an unrelated reason). Linear Search's own Complexity section states the matching bound for an unsorted array directly, with the other technique this page covers next: "an adversary argument shows why... nothing sub-O(n) can be made worst-case correct without more structure... than an unordered list provides."

Finding the max: a different kind of argument

Not every lower bound needs a decision tree. Finding the largest of n distinct elements by pairwise comparison needs at least n − 1 comparisons, and the cleanest proof doesn't count leaves at all — it counts eliminations. Every comparison has exactly one loser, and the loser is thereby proven not to be the maximum (something in the input is bigger than it). The algorithm can only be sure it has found the true maximum once every other element has lost at least one comparison — if some element x never lost a single comparison, nothing in the run has ruled out x being the actual largest, and an adversary could always have arranged the hidden values to make that true. There are n − 1 elements that aren't the maximum, each needs its own losing comparison, and each comparison produces only one loser — so at least n − 1 comparisons are unavoidable. A plain linear scan, keeping a running maximum and comparing each new element against it, hits that bound exactly: n − 1 comparisons, not one more. The identical argument holds for the minimum by symmetry — exactly what Selection Sort's own scan computes every pass, and its own Pitfalls section already measures that scan's comparison count directly (n(n-1)/2 total, confirmed by instrumenting its reference implementation). Selection Sort is just that single optimal n-1-comparison scan, run from scratch n separate times on a shrinking remainder — which is exactly why its total is quadratic even though no individual pass ever wastes a comparison.

How some algorithms escape the bound

Counting Sort and Radix Sort both run in time linear in n (plus the key-range or digit-count terms each page's own Complexity section spells out), which looks like a contradiction of the Ω(n log n) bound just derived above, until the model gets checked rather than the arithmetic: that bound only binds an algorithm whose only way of learning anything about two elements is asking "which is bigger?" and getting back one bit. Counting Sort never asks that question — it reads a key's actual value and uses it directly as an array index, a strictly more powerful primitive than a yes/no comparison, and one the decision-tree argument's leaf-counting proof never assumed existed. Counting Sort's own Pitfalls section names this precisely: "the Ω(n log n) bound isn't violated, it's dodged." Radix Sort's own Complexity section puts the same idea even more bluntly about itself: "this isn't a comparison sort at all." Escaping a lower bound always works this way — never by writing a cleverer algorithm inside the same model, only by changing what the model allows the algorithm to do in the first place. See Choosing a Comparison Sort for the other direction of this same line: all twelve of that page's entries stay inside the comparison model on purpose, and its own closing line notes plainly that none of them beat O(n log n) because none of them even try to.

Pitfalls

A lower bound is a claim about every possible algorithm in a model, not about the ones anyone has actually written. "Ω(n log n) comparisons" doesn't mean "every sort on this site happens to need at least that many" — it rules out every comparison-based sort that could ever be written, discovered or not, the same way a proof that no integer solves x² = 2 rules out every integer, not just the ones someone has already tried.

The bound is tied to a model, and the model is a choice, not a law of nature. Changing what one step is allowed to see — array indexing instead of pairwise comparison, a word-RAM machine instead of a comparison oracle, randomization, parallelism — can and does produce algorithms that beat a bound proved under a narrower model, without that bound ever having been wrong. The Counting Sort/Radix Sort pair above is this site's own example; checking which model a stated lower bound actually assumes is the one step worth never skipping before citing it as "provably impossible to beat."

The decision-tree argument above bounds the worst case specifically — it doesn't by itself say anything about the average case. A tree's height is set by its single deepest leaf; the worst-case argument only forces that one deepest leaf to exist, not that most leaves sit that deep. (Average-case Ω(n log n) for comparison sorting is also true and provable, by a separate argument over the tree's average leaf depth rather than its height — real, just not the argument derived on this page.)

An adversary argument has to answer consistently, not just unhelpfully. The finding-the-max argument above works because "every non-maximum element needs its own losing comparison" is true regardless of which element turns out to be the maximum — the adversary never has to commit to specific values until forced to, but every answer it has already given has to stay consistent with some real assignment of values once the algorithm stops. Linear Search's own version works the same way: the adversary can always answer "not yet" to any comparison that hasn't looked at every remaining candidate, because it could always place the target in whichever unchecked slot makes that answer true.