3
$\begingroup$

Given the following recurrence:

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

How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion we pay $n^2$ and we have $n$ steps of recursion therefore having: $n \times n^2 = n^3$.

I would even expect this to be $\Theta(n^3)$, but I can't even prove $O(n^3)$.

I tried with the guess:

$$ T(n) \leq n^3 + n^2 \cdot c_1 + n \cdot c_2 + c_3 $$

but that yields:

$$ T(n) \leq n^3 + n^2 \cdot (3 + c_1) + n \cdot (c_2 - 2c_1 -1) + (c_1 - 1 - c_2 + c_3) $$

which yields:

  1. $c_1 = c_1 + 3$
  2. $c_2 = c_2 - 2c_1 - 1$
  3. $c_3 = c_1 - 1 - c_2 + c_3$

But even from the very first ($c_1 = c_1 + 3$) we find that no $c_1$, $c_2$ or $c_3$ satisfy the equations.

What did I do wrong?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

If $T(n)$ is $O(n^3)$, then with a coefficient to $n^3$:

$$ T(n) \leq n^3 c_3 + n^2 c_2 + n c_1 + c_0 $$ So, expanding $T(n+1)$: $$\begin{align*} T(n + 1) &\leq (n + 1)^3 c_3 + (n + 1)^2 c_2 + (n + 1) c_1 + c_0 \\ T(n) + (n + 1)^2 &\leq n^3 c_3 + 3n^2 c_3 + 3n c_3 + c_3 + n^2 c_2 + 2n c_2 + c_2 + n c_1 + c_1 + c_0\end{align*} $$

Leading us to:

$$ T(n) \leq n^3 c_3 + n^2 (3c_3 + c_2 - 1) + n (3c_3 + 2c_2 + c_1 - 2) + c_3 + c_2 + c_1 + c_0 - 1 $$

Therefore:

  1. $ c_3 = c_3 $
  2. $ c_2 = 3c_3 + c_2 - 1 $
  3. $ c_1 = 3c_3 + 2c_2 + c_1 - 2 $
  4. $ c_0 = c_3 + c_2 + c_1 + c_0 - 1$

Solving:

$$\begin{align} c_3 &= 1/3 \\ c_2 &= 1/2 \\ c_1 &= 1/6 \end{align} \\ T(n) \leq n^3/3 + n^2/2 + n/6 + c_0 = \frac{n(n + 1)(2n + 1)}{6} + c_0 $$

$\endgroup$
9
  • 1
    $\begingroup$ I'm not sure why you are expanding $T(n+1)$ though. $\endgroup$
    – Shoe
    Jul 11, 2015 at 1:04
  • $\begingroup$ @Jefffrey why not? Personal preference for $-$ over $+$, I suppose. $\endgroup$
    – muru
    Jul 11, 2015 at 1:07
  • $\begingroup$ @Jefffrey Ok, I'll bite. What would you do instead, and how would it be better? $\endgroup$
    – muru
    Jul 11, 2015 at 1:25
  • $\begingroup$ You have a typo: $T(n) = O(n^3)$ rather than $T(n) = O(n)$. $\endgroup$ Jul 11, 2015 at 3:23
  • 1
    $\begingroup$ @Jefffrey sure, it has $T(n-1)$ in the recursive step. What of it? I can replace $n$ with $y+1$ and get an equivalent recursion, and expanding $(y+1)^3$ frees me from juggling the signs involved in $(n-1)^3$. $\endgroup$
    – muru
    Jul 11, 2015 at 11:08
0
$\begingroup$

Hint: Expanding the recurrence, we get that $$ T(n) = n^2 + (n-1)^2 + \cdots + 1^2 + T(0). $$ It is known that $$\sum_{m=1}^n m^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3).$$

$\endgroup$
2
  • $\begingroup$ Does that mean that it's not possible to use the substitution method here? $\endgroup$
    – Shoe
    Jul 10, 2015 at 20:24
  • $\begingroup$ Since there is an exact formula, you can definitely use the substitution method. You must have made a mistake in your calculation above. $\endgroup$ Jul 10, 2015 at 20:33

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.