The tightest lower bound on the number of comparisons, in the worst case, for…
2004
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
- A.
n
- B.
n2
- C.
n log n
- D.
n log2 n
Attempted by 157 students.
Show answer & explanation
Correct answer: C
Key idea: model any comparison-based sorting algorithm as a binary decision tree and count leaves.
Each internal node of the decision tree is a comparison; each leaf corresponds to one possible output order of the input.
There are n! distinct permutations of n elements, so the tree must have at least n! leaves to produce every possible sorted order.
A binary tree of height h has at most 2^h leaves, so 2^h ≥ n!, hence h ≥ log2(n!).
Using Stirling's approximation (or standard bounds) gives log2(n!) = Θ(n log n).
Therefore the worst-case number of comparisons for any comparison-based sorting algorithm is at least Θ(n log n), i.e., a lower bound of order n log n.
This bound is tight because comparison sorts such as merge sort achieve O(n log n), so the tightest worst-case bound is Θ(n log n).