8
$\begingroup$

I'm looking for a $\Theta$ approximation of $$T(n) = T(n-1) + cn^{2}$$

This is what I have so far:

$$ \begin{align*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex] T(n-2) &= T(n-3) + c(n-2)^2\\ T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex] T(n-3) &= T(n-4) + c(n-3)^2 \\ T(n) &= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2 \end{align*} $$

So, at this point I was going to generalize and substitute $k$ into the equation.

$$T(n)= T(n-k) + (n-(k-1))^2 + c(k-1)^2$$

Now, I start to bring the base case of 1 into the picture. On a couple of previous, more simple problems, I was able to set my generalized k equation equal to 1 and then solve for $k$. Then put $k$ back into the equation to get my ultimate answer.

But I am totally stuck on the $(n-k+1)^2$ part. I mean, should I actually foil all this out? I did it and got $k^2-2kn-2k+n^2 +2n +1 = 1$. At this point I'm thinking I totally must have done something wrong since I've never see this in previous problems.

Could anyone offer me some help with how to solve this one? I would greatly appreciate it. I also tried another approach where I tried to set $n-k = 0$ from the last part of the equation and got that $k = n$. I plugged n back into the equation towards the end and ultimately got $n^2$ as an answer. I have no clue if this is right or not.

I am in an algorithms analysis class and we started doing recurrence relations and I'm not 100% sure if I am doing this problem correct. I get to a point where I am just stuck and don't know what to do. Maybe I'm doing this wrong, who knows. The question doesn't care about upper or lower bounds, it just wants a theta.

$\endgroup$
1
  • $\begingroup$ See this question for plenty of material on solving recurrences. $\endgroup$
    – Raphael
    Commented Oct 25, 2012 at 10:52

3 Answers 3

10
$\begingroup$

Just continue your reasoning as follows.

\begin{eqnarray} T(n) &=& T(n-1) + cn^2 \\ &=& T(n-2) + c(n-1)^2 + cn^2 \\ &=& \ldots \\ &=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\ &=& T(0) +c\sum_{1\leq i\leq n} i^2. \end{eqnarray}

Do you know how to simplify this using the addition formula for the first $n$ squares?

$\endgroup$
2
  • $\begingroup$ I'm not entirely sure what you mean by the addition formula for the first n squares. Is that like n(n+1)/2 type stuff? $\endgroup$ Commented Oct 24, 2012 at 3:10
  • $\begingroup$ Exactly, that's right $\endgroup$
    – PKG
    Commented Oct 24, 2012 at 4:30
2
$\begingroup$

sometimes formulas are hard to remember, integration could be handy -- $$\sum_{i=1}^n i^2 \approx \int_1^n i^2 di = \frac{1}{3}i^3 \bigg]_1^n = \frac{1}{3}(n^3 - 1) \leq cn^3 = O(n^3)$$

$\endgroup$
2
  • $\begingroup$ I love this method but it doesn't give you $\Omega$ bound. $\endgroup$ Commented Jul 13, 2013 at 6:30
  • 2
    $\begingroup$ @PratikDeoghare yes it does. because the function $f(i) = i^2$ is monotone. $\endgroup$ Commented Sep 28, 2013 at 12:26
2
$\begingroup$

More generally, any recurrence relation of the form $T(n) = T(n-1) + f(n)$ has the solution $T(n) = \sum_{i=0}^n f(i)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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