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