Show that the solution of \(T(n) = T(n - 1) + n\) is \(O(n^2)\).
Let us assume \(T(n) \le cn^2\) for all \(n \ge n_0\), where \(c\) and \(n_0\) are positive constants. We’ll specify the constants later based on our induction requirements.
Hence, \(T(n - 1) \leq c(n - 1)^2\)
Therefore, we can write:
\[\begin {aligned} T(n) & \le c(n - 1)^2 + n \\ & = cn^2 - 2cn + c + n \\ & = cn^2 - (n(2c - 1) - c) \\ & \le cn^2 \end {aligned}\]The last step holds as long as \((n(2c - 1) - c) \ge 0\). We can use this to specify \(c\) and \(n_0\).
If we pick \(c = 1\), then we need \(n - 1 \ge 0\). Which is possible as long as \(n \ge 1 = n_0\).
Solving Without Substitution
This particular problem can be solved using a much simpler method, that does not use substitution.
We can safely assume \(T(0) = k\), where \(k\) is positive constant, as for input size zero we need to do only a constant amount of work, e.g. checking input size and returning.
Therefore:
\[\begin{aligned} T(1) &= T(0) + 1 = k + 1 \\ T(2) &= T(1) + 2 = k + 1 + 2 \\ T(3) &= T(2) + 3 = k + 1 + 2 + 3 \\ \cdots \\ T(n) &= T(n - 1) + n = k + 1 + 2 + 3 + \cdots + n \\ &= k + \frac {n(n + 1)} 2 \\ &= \Theta(n^2) \end{aligned}\]