Question Detail: See title. I’m trying to apply the method from this question. What I have so far is this, but I don’t know how to proceed from here on: T(n) = T(n-1) + n2 T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 – 2n + 1 T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 – 4n + 4 T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 – 6n + 9 Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives: T(n) = T(n-2) + 2n2 – 2n + 1 T(n) = T(n-3) + 3n2 – 6n + 5 T(n) = T(n-4) + 4n2 – 12n + 14 Now I have to find a pattern but I don’t really know how to do that. What I got is: T(n) = T(n-k) + kn2 – …???
Asked By : Ken
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43434
Answered By : Rick Decker
Don’t expand the squared terms; it’ll just add confusion. Think of the recurrence as $$ T(fbox{foo}) = T(fbox{foo}-1)+fbox{foo};^2 $$ where you can replace foo with anything you like. Then from $$ T(n)=T(n-1)+n^2 $$ you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding $$ T(n) = [T(n-2) + (n-1)^2]+n^2 = T(n-2)+(n-1)^2+n^2 $$ and similarly $$begin{align} T(n) &= T(n-2)+(n-1)^2+n^2 &= T(n-3)+(n-2)^2+(n-1)^2+n^2 &= T(n-4)+(n-3)^2+(n-2)^2+(n-1)^2+n^2 end{align}$$ and in general you’ll have $$ T(n) = T(n-k)+(n-k+1)^2+(n-k+2)^2+dotsm+(n-1)^2+n^2 $$ Now if we let $k=n$ we’ll have $$ T(n) = T(0)+1^2+2^2+3^2+dotsm+n^2 $$ Now if you just need an upper bound for $T(n)$ observe that $$ 1^2+2^2+3^2+dotsm+n^2le underbrace{n^2+n^2+n^2+dotsm+n^2}_n=n^3 $$ so we conclude that $T(n)=O(n^3)$, in asymptotic notation. For a more exact estimate, you can look up the equation for the sum of squares: $$ 1^2+2^2+dotsm+n^2=frac{n(n+1)(2n+1)}{6} $$ so $$ T(n)=T(0)+frac{n(n+1)(2n+1)}{6} $$
