7
$\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$
  • $\begingroup$ See this question for plenty of material on solving recurrences. $\endgroup$ – Raphael Oct 25 '12 at 10:52
8
$\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$
  • $\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$ – Tastybrownies Oct 24 '12 at 3:10
  • $\begingroup$ Exactly, that's right $\endgroup$ – PKG Oct 24 '12 at 4:30
3
$\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$
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$
  • $\begingroup$ I love this method but it doesn't give you $\Omega$ bound. $\endgroup$ – Pratik Deoghare Jul 13 '13 at 6:30
  • 1
    $\begingroup$ @PratikDeoghare yes it does. because the function $f(i) = i^2$ is monotone. $\endgroup$ – Igor Shinkar Sep 28 '13 at 12:26

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.