GATE CS 1990 Q3-v — Searching, Sorting, Hashing

The optimal worst-case time complexity of any comparison-based sorting algorithm is $\Theta(n \log n)$. This limit is established using the decision tree model:

1. To sort $n$ distinct elements, there are $n!$ possible permutations (outcomes).
2. A binary decision tree representing the comparison-based sorting must have at least $n!$ leaf nodes to distinguish all possible sorted orders.
3. The height of a binary tree with $L$ leaves is at least $\lceil \log_2 L \rceil$. Therefore, the height $h$ (representing the minimum number of comparisons in the worst case) satisfies:$$h \ge \log_2(n!)$$
4. Using Stirling's approximation, we have:$$\log_2(n!) \approx n \log_2 n - n \log_2 e = \Theta(n \log n)$$

Since algorithms like Merge Sort and Heap Sort achieve a worst-case time complexity of $\Theta(n \log n)$, this bound is tight. Thus, the complexity of optimal comparison-based sorting is $\Theta(n \log n)$.