Show that \(\textsc{Randomized-Quicksort}\)’s expected running time is \(\Omega(n \lg n)\).
To establish a lower bound on the expected running time, we’ll show that the expected number of comparisons performed by randomized quicksort is at least \(\Omega(n \lg n)\).
From Section 7.4.2, we know the expected running time is \(O(n \lg n)\). The interesting direction is the matching lower bound, and there are two ways to see it.
The first is a counting argument that applies to any comparison-based sort, randomized or not. Sorting must distinguish all \(n!\) orderings of the input, and every comparison has only two outcomes, so a run that makes \(c\) comparisons can tell apart at most \(2^c\) orderings. A randomized algorithm is just a probability distribution over such comparison sequences, and on a uniformly random input the expected number of comparisons is at least the average leaf depth of a binary tree with \(n!\) leaves. That average depth is \(\Omega(\lg(n!))\), and by Stirling’s approximation \(\lg(n!) = \Theta(n \lg n)\), so the expected number of comparisons is \(\Omega(n \lg n)\).
The second way is to lower-bound the expected comparison count of randomized quicksort directly. From Section 7.4.2 the expected number of comparisons is:
\[E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1}\]Group the pairs by their gap \(d = j - i\). For each gap \(d\) there are \(n - d\) pairs, so:
\[\begin{align*} E[X] &= \sum_{d=1}^{n-1} (n-d) \cdot \frac{2}{d+1} \end{align*}\]Now keep only the terms with \(d \leq n/2\), where \(n - d \geq n/2\). Dropping the rest only decreases the sum:
\[\begin{align*} E[X] &\geq \sum_{d=1}^{n/2} \frac{n}{2} \cdot \frac{2}{d+1} \\ &= n \sum_{d=1}^{n/2} \frac{1}{d+1} \\ &= n \left(H_{n/2+1} - 1\right) \\ &= \Omega(n \lg n) \end{align*}\]where \(H_m = \sum_{k=1}^{m} 1/k = \ln m + O(1)\) is the \(m\)-th harmonic number. The harmonic sum grows like \(\lg n\), which is exactly where the extra logarithmic factor comes from.
Combining either lower bound with the upper bound \(E[X] = O(n \lg n)\) from Section 7.4.2:
\[E[X] = \Theta(n \lg n)\]Therefore, the expected running time of randomized quicksort is \(\Theta(n \lg n)\).