Use the substitution method to prove that the recurrence \(T(n) = T(n-1) + \Theta(n)\) has the solution \(T(n) = \Theta(n^2)\), as claimed at the beginning of Section 7.2.
This recurrence describes quicksort’s worst-case behavior when partitions are maximally unbalanced. We’ll prove both the upper bound \(T(n) = O(n^2)\) and the lower bound \(T(n) = \Omega(n^2)\) using the substitution method.
For the upper bound, we assume \(\Theta(n) \leq cn\) for some constant \(c > 0\). We guess that \(T(n) \leq dn^2\) for some constant \(d > 0\), and prove this by induction.
Base case: For small \(n\), we can choose \(d\) large enough that \(T(n) \leq dn^2\) holds. E.g., \(n = 1\) and \(d = 2\).
Inductive step: Assume \(T(k) \leq dk^2\) for all \(k < n\). We need to show \(T(n) \leq dn^2\).
\[\begin{align*} T(n) &= T(n-1) + cn \\ &\leq d(n-1)^2 + cn \\ &= d(n^2 - 2n + 1) + cn \\ &= dn^2 - 2dn + d + cn \\ &= dn^2 - (2d - c)n + d \end{align*}\]For this to be \(\leq dn^2\), we need:
\[-(2d - c)n + d \leq 0\]This holds when \(d \geq c/2\) and \(n \geq 1\), since then \((2d - c)n \geq d\). Therefore, \(T(n) = O(n^2)\).
For the lower bound, we assume \(\Theta(n) \geq cn\) for some constant \(c > 0\). We guess that \(T(n) \geq dn^2\) for some constant \(d > 0\).
Inductive step: Assume \(T(k) \geq dk^2\) for all \(k < n\).
\[\begin{align*} T(n) &= T(n-1) + cn \\ &\geq d(n-1)^2 + cn \\ &= dn^2 - 2dn + d + cn \\ &= dn^2 + (c - 2d)n + d \end{align*}\]For this to be \(\geq dn^2\), we need:
\[(c - 2d)n + d \geq 0\]Choosing \(d \leq c/3\) (a small enough constant) ensures this inequality holds for all \(n \geq 1\). Therefore, \(T(n) = \Omega(n^2)\).
Since \(T(n) = O(n^2)\) and \(T(n) = \Omega(n^2)\), we conclude that \(T(n) = \Theta(n^2)\).