HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Proving the lower bound of compares in comparison based sorting

Submitted by: @import:stackexchange-cs··
0
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.