GATE CS 2004 Q29 — Searching, Sorting, Hashing

The worst-case lower bound for any comparison-based sorting algorithm can be established using the decision tree model.

For an input sequence of $n$ distinct elements, there are $n!$ possible permutations. Any comparison-based sorting algorithm must be able to distinguish between all of these $n!$ permutations to correctly sort the input.

In a binary decision tree representing the comparisons:

• Each internal node represents a comparison between two elements.
• Each leaf node represents a unique sorted permutation of the input.
• If the height of the decision tree is $h$, the maximum number of leaves it can have is $2^h$.

To successfully sort all possible inputs, the number of leaves must be at least the number of permutations:

Taking the logarithm (base 2) on both sides:

Using Stirling's approximation, we know that:

Thus, the minimum height $h$ (which represents the worst-case number of comparisons) is of the order of $\Omega(n \log n)$. Therefore, the tightest lower bound is of the order of $n \log n$.