0
$\begingroup$

I have $$T(n)=T(n-1)+n^{2}$$ And I know, by drawing the recursion tree that this is $\Theta (n^{3})$ However, if I try claiming that it's $O(n^{2})$ through induction: $$T(n)\le c(n-1)^{2}+n^{2}\le cn^{2}$$ which evaluates to $$c\ge \frac{n^2}{2n-1}$$ Which makes $c>0$ for all $n>1$ and concludes that the recurrence is $O(n^{2})$ which is not correct. So what am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

The error is that $c(n-1)^2 + n^2 = cn^2 - 2cn + c +n^2 \leq (c+1)n^2$, so the constant $c$ is in fact no constant, since it grows with every step.

So you get that when $n$ increases by 1, $c$ also does, so you have $O(n) \cdot n^2$, so $O(n^3)$.

$\endgroup$
4
  • $\begingroup$ So in cases like this we find Big-Oh for c and use that to deduce the Big-Oh for the original recurrenc, right? $\endgroup$
    – Essam
    Dec 7, 2020 at 13:09
  • $\begingroup$ You can think of it that way, but I think if you don't use the Master Theorem, then the best way is to unfold the recurrence or look at how it grows with each step. If you know that some recursive equation is $O(f)$, then you can try proving it the way you tried, but make sure that constants are actually constants. $\endgroup$ Dec 7, 2020 at 13:12
  • $\begingroup$ Now I understand, so it can be a function in n, but has to be O(1). How about checking that the constant is positive, do we have to check that it's positive for all n greater than some n_nought? $\endgroup$
    – Essam
    Dec 7, 2020 at 13:56
  • $\begingroup$ Well, if we are talking Computer Science, then usually recursive relations describe the running time of an algorithm, and so they should be positive. Saying that something can be a function in $n$ but be $O(1)$ is kinda pointless, because if something is $O(1)$, then it is a constant, like $3$, but the number $3$ can be called a function in any argument. $\endgroup$ Dec 7, 2020 at 16:44

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.