# Proving the lower bound of compares in comparison based sorting

I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help is appreciated! • 1. Please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX). You can still keep the picture of the tree, but transcribe the text. 2. Please cite where this is in their book (section number, page numbers). – D.W. Oct 26 '14 at 4:47

## 2 Answers

A sorting algorithm using at most $h$ comparisons on all inputs corresponds to a tree of height at most $h$. Such a tree has at most $2^h$ leaves. On the other hand, each permutation of $1,\ldots,N$ must land at a different leaf, and so there must be at least $N!$ leaves. Putting these together, we deduce that $2^h \geq N!$ and so $h \geq \log_2 N! = \Omega(N\log N)$ (using Stirling's approximation). So every sorting algorithm must use at least $\log_2 N! = \Omega(N\log N)$ comparisons in the worst case (on some inputs it can use less).

• Thanks Yuval, but I still don't get it why $h\ge log_2N!$ would mean the sorting must use at least $log_2N!$ comparisons. In the proof, I think it assumes that the comparison number is equal to $log_2(number~of~leaves)$. I want to know the reasoning behind this assumption. – addego Oct 26 '14 at 4:32
• By definition $h$ is a number such that the given sorting algorithm uses at most $h$ comparisons on all inputs (if you want a proper definition, $h$ is the maximum number of comparisons the algorithm uses on any input). It is definitely not the case that the number of comparisons is equal to $\log_2$ of the number of leaves; the latter need not even be an integer! The number of comparisons isn't directly related to the number of leaves but rather to the height of the tree; if the tree is shallow then there cannot be many leaves. – Yuval Filmus Oct 26 '14 at 5:10
• I can understand what you have said so far. Let me put my question in another way, there are so many values less than $2^h$, e.g., $2^h - 1$, or $N! + 1$, but why is the number of leaves (N!) is selected to give the lower bound? For $h$, I can understand this means the height of the tree, but what does $log_2N!$ mean? – addego Oct 26 '14 at 6:13
• The number of leaves is relevant since we can prove that there must be at least $N!$ leaves. This allows us to give a lower bound on $h$. If we could prove the lower bound through some other quantity, we would have used the other quantity, but our proof works through the number of leaves. The quantity $\log_2 N!$ doesn't mean anything. Rather, if a binary tree has at least $N!$ leaves, then its height must be at least $\log_2 N!$. – Yuval Filmus Oct 26 '14 at 6:28

Assumptions:

• The input consists of $n$ values which can potentially be distinct.
• The only way to obtain information about the order of values is to apply a function which compares two values and returns a boolean indicating whether the first value is less than or equal to the second value. (This is what “comparison sort” means.)

Given the first assumption, there are $n!$ possible permutations of the input (i.e. there are $n!$ ways to reorder the input). If a run of the algorithm makes $k$ comparisons, then it can only distinguish between $2^k$ different sets of permutations, since each comparison at most multiplies the number of distinguishable permutations by 2. If $2^k \lt n!$, then by the pigeonhole principle, there exist two permutations of the input which lead to the same state of the program implementing the algorithm. Since the algorithm has to work for inputs where all values are distinct, these two permutations cannot both be in the desired order.

For example, suppose you're sorting $4$ values. There are $4! = 24$ permutations. The first comparison divides the set of permutations into two sets, at least one of which must have at least $12$ elements. All the permutations in a given set are indistinguishable without further comparisons. The second comparison divides the set in two, which in the worst case leaves at least $6$ indistinguishable permutations. Another division reduces the worst case set size to $3$, another one to $2$, and a final one may be able to reduce the set size to $1$, uniquely identifying the permutation.

The upshot is that any correct sorting algorithm under these assumptions must execute a number of comparisons $k$ in the worst case such that $2^k \ge n!$. The number of comparisons is thus at least $\log_2(n!)$. By Stirling's approximation and a bit of simple calculus, $\_log_2(n!) = \Omega(n \log_2))$. This proves that a comparison sort has a worst case time complexity lower bound of $\Omega(n \log(n))$, by the number of comparisons alone.

Relaxing either assumption allows faster sorting algorithms. In practice, these assumptions model the reality well most of the time.

• Exercise: suppose that instead of a less-than function returning true or false, we have a binary compare function that returns “less”, “equal” or “greater”. What is the lower bound on the worst-case number of calls to the comparison function? Does this improve the asymptotic bound?
• There are scenarios where the first assumption doesn't hold. For example, to sort a list of values which are all 0 or 1, it's enough to put all the 0's before the 1's, which can be done in linear time. More generally, if there are $n$ values to sort but only at most $p$ distinct values, it's possible to sort them in $O(n \log(p))$. Radix sort achieves this. The proof above doesn't apply because it's ok to end up with a set containing multiple potential permutations, if all the permutations only move around values that are equal.