Show that in the recurrence
\(T(n) = \max_{0 \leq q \leq n-1} (T(q) + T(n-q-1)) + \Theta(n)\),
\(T(n) = \Omega(n^2)\).
We’ll use the substitution method to prove the lower bound \(T(n) = \Omega(n^2)\). This requires showing that \(T(n) \geq cn^2\) for some constant \(c > 0\) and sufficiently large \(n\).
The recurrence represents quicksort’s worst-case running time, where we take the maximum over all possible partition outcomes. Because \(T(n)\) is the maximum over \(q\), it is at least as large as the value produced by any single choice of \(q\). So to prove a lower bound, we just need one particular choice of \(q\) that already forces \(\Omega(n^2)\); we don’t have to reason about all of them.
The most lopsided partition occurs when \(q = 0\) or \(q = n-1\), leaving one subproblem of size \(n-1\) and one of size \(0\). Let’s use \(q = 0\):
\[T(n) \geq T(0) + T(n-1) + cn\]where we’ve replaced \(\Theta(n)\) with \(cn\) for some constant \(c > 0\).
Since \(T(0) = \Theta(1)\), we can write:
\[T(n) \geq T(n-1) + cn\]Our guess is that \(T(n) \geq dn^2\) for some constant \(d > 0\). For small \(n\) this holds trivially by choosing \(d\) small enough, which takes care of the base case. For the inductive step, assume \(T(k) \geq dk^2\) for all \(k < n\) and show that the same bound holds at \(n\):
\[\begin{align*} T(n) &\geq T(n-1) + cn \\ &\geq d(n-1)^2 + cn \\ &= d(n^2 - 2n + 1) + cn \\ &= dn^2 - 2dn + d + cn \\ &= dn^2 + (c - 2d)n + d \end{align*}\]For this to be at least \(dn^2\), we need:
\[(c - 2d)n + d \geq 0\]Choosing \(d \leq c/3\) ensures this inequality holds for all \(n \geq 1\):
\[(c - 2 \cdot c/3)n + c/3 = \frac{cn}{3} + \frac{c}{3} = \frac{c(n+1)}{3} > 0\]Therefore, \(T(n) \geq dn^2\) for \(d = c/3\), which proves \(T(n) = \Omega(n^2)\).
From Section 7.4.1, we know \(T(n) = O(n^2)\). Combined with our lower bound \(T(n) = \Omega(n^2)\), we conclude:
\[T(n) = \Theta(n^2)\]This confirms that quicksort’s worst-case running time is quadratic, which occurs when the input is already sorted (or reverse sorted) and we always pick the last element as the pivot.