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.
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.
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):
a ≤ b?
b ≤ c?
a ≤ c?
a ≤ c?
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.
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."
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.
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.
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.