patternModerate
Proving the lower bound of compares in comparison based sorting
Viewed 0 times
provingsortingtheboundlowercomparescomparisonbased
Problem
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!
Solution
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).
Context
StackExchange Computer Science Q#32311, answer score: 16
Revisions (0)
No revisions yet.