Exercise 7.2.1

Use the substitution method to prove that the recurrence T(n)=T(n−1)+Θ(n)T(n) = T(n-1) + \Theta(n) has the solution T(n)=Θ(n2)T(n) = \Theta(n^2), as claimed at the beginning of section 7.2

We represent Θ(n)\Theta(n) as c2nc_2n and we guess that T(n)≤c1n2T(n) \le c_1n^2

T(n)=T(n−1)+c2n≤c1(n−1)2+c2n=c1n2−2c1n+c1+c2n(2c1>c2,n≥c1/(2c1−c2))≤c1n2 \begin{aligned} T(n) &= T(n-1) + c_2n \\ &\le c_1(n-1)^2 + c_2n \\ &= c_1n^2 - 2c_1n + c_1 + c_2n & (2c_1 > c_2, n \ge c_1/(2c_1 - c_2))\\ &\le c_1n^2 \end{aligned}