Per the lecture, the worst-case lower bound on the number of comparisons made by any comparison-based sort on n elements is
A$\Omega(n \log n)$
B$\Omega(n)$
C$\Omega(n^2)$
D$\Omega(\log n)$
Answer & Solution
Correct answer: A. $\Omega(n \log n)$
Each pairwise comparison can split the space of possible orderings by at most a factor of 2, and there are n! possible orderings of n distinct elements. So any decision tree resolving them needs at least log_2(n!) ≈ n log n levels. Hence Ω(n log n) is the lower bound. Linear or sub-linear bounds are impossible without using non-comparison information.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for