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$
3
  • 1
    $\begingroup$ possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$
    – D.W.
    Jun 10 '15 at 2:07
  • $\begingroup$ @D.W. Since the OP did actually try and do something (and Rick's answer is outstanding), I think we can keep this one. $\endgroup$
    – Raphael
    Jun 10 '15 at 7:40
  • $\begingroup$ Suggested to use Tex formatting for mathematical formulae. $\endgroup$
    – hola
    Nov 23 '19 at 10:57
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} $$

$\endgroup$
1
  • $\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).

$\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.