[Solved]: Proving the lower bound of compares in comparison based sorting

Problem Detail: 

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!

Asked By : addego

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32311

 Ask a Question

 Download Related Notes/Documents