Show that quicksort’s best-case running time is \(\Omega(n \lg n)\).
To establish a lower bound on quicksort’s best-case running time, we’ll show that even in the most favorable scenario, the algorithm must perform at least \(\Omega(n \lg n)\) work.
Quicksort’s best case occurs when partitions are as balanced as possible at every level. The most balanced partition splits the array into two nearly equal halves, with subarrays of sizes \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil - 1\) (accounting for the pivot element).
For simplicity, assume perfect splits of size \(n/2\) each. The recurrence for the best case is:
\[T(n) = 2T(n/2) + \Theta(n)\]We’ll prove that \(T(n) \geq cn \lg n\) for some constant \(c > 0\) using the substitution method. Our guess is that \(T(n) \geq dn \lg n\) for some constant \(d > 0\). Assume the bound holds for all \(k < n\), that is \(T(k) \geq dk \lg k\).
Since \(\Theta(n) \geq cn\) for some constant \(c > 0\) (by definition of \(\Theta\)), we have:
\[\begin{align*} T(n) &= 2T(n/2) + \Theta(n) \\ &\geq 2d(n/2)\lg(n/2) + cn \\ &= dn(\lg n - \lg 2) + cn \\ &= dn \lg n - dn + cn \\ &= dn \lg n + (c - d)n \end{align*}\]For this to be at least \(dn \lg n\), we need:
\[(c - d)n \geq 0\]This holds when \(d \leq c\). Choosing \(d = c\) gives us \(T(n) \geq cn \lg n\), proving \(T(n) = \Omega(n \lg n)\).
Quicksort’s best-case performance exactly matches this lower bound. From the master theorem, the recurrence \(T(n) = 2T(n/2) + \Theta(n)\) has solution \(T(n) = \Theta(n \lg n)\).
Combined with the upper bound \(T(n) = O(n \lg n)\) (which follows from the master theorem), we have:
\[T(n) = \Theta(n \lg n)\]This proves that quicksort’s best-case running time is both \(\Omega(n \lg n)\) and \(O(n \lg n)\), making it exactly \(\Theta(n \lg n)\).