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$
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$
  • 1
    $\begingroup$ I'm not sure why you are expanding $T(n+1)$ though. $\endgroup$ – Shoe Jul 11 '15 at 1:04
  • $\begingroup$ @Jefffrey why not? Personal preference for $-$ over $+$, I suppose. $\endgroup$ – muru Jul 11 '15 at 1:07
  • $\begingroup$ @Jefffrey Ok, I'll bite. What would you do instead, and how would it be better? $\endgroup$ – muru Jul 11 '15 at 1:25
  • $\begingroup$ You have a typo: $T(n) = O(n^3)$ rather than $T(n) = O(n)$. $\endgroup$ – Yuval Filmus Jul 11 '15 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 '15 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$
  • $\begingroup$ Does that mean that it's not possible to use the substitution method here? $\endgroup$ – Shoe Jul 10 '15 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$ – Yuval Filmus Jul 10 '15 at 20:33

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.