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(Nlog N)$ (using Stirling’s approximation). So every sorting algorithm must use at least $log_2 N! = Omega(Nlog 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
