# What's the bound of the following recurrence?

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 * 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) <= n^3 + n^2 * c1 + n * c2 + c3
``````

but that yields:

``````T(n) <= n^3 + n^2 * (3 + c1) + n * (c2 - 2c1 -1) + (c1 - 1 - c2 + c3)
``````

which yields:

1. `c1 = c1 + c`
2. `c2 = c2 - 2c1 - 1`
3. `c3 = c1 - 1 - c2 + c3`

But even from the very first (`c1 = c1 + c`) we find that no `c1`, `c2` or `c3` satisfy the equations.

What did I do wrong?

• This question would be more appropriate at Computer Science. If you ask there please search for similar questions first and read their help center before asking. Also, delete this question since cross-posting is not advised. – user22815 Jul 10 '15 at 16:20
• @Snowman Isn't this a conceptual question about software development? Should I modify my question so that I invent an algorithm for this recurrence and then it becomes a question about software development? – Shoe Jul 10 '15 at 16:34