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 =
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)
c1 = c1 + c
c2 = c2 - 2c1 - 1
c3 = c1 - 1 - c2 + c3
But even from the very first (
c1 = c1 + c) we find that no
c3 satisfy the equations.
What did I do wrong?