6
$\begingroup$

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 - ...???

$\endgroup$
13
$\begingroup$

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^2\le \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} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Really clear explanation, thanks a lot! $\endgroup$ – Ken Jun 9 '15 at 22:48
5
$\begingroup$

Just start with:

$\begin{align} T(k) - T(k - 1) &= k^2 \\ \sum_{1 \le k \le n} (T(k) - T(k - 1)) &= \sum_{1 \le k \le n} k^2 \\ T(n) - T(0) &= \frac{n (n + 1) (2 n + 1)}{6} \end{align}$

by telescoping (see also square piramidal numbers).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.