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?

  • 3
    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
  • What about this question? – Shoe Jul 10 '15 at 16:36
  • 2
    this is a math question that reminds me of my Algorithms class from years ago. Recurrence relations are actually a Linear Algebra concept, although they are used in Computer Science as well. Regardless, I have never seen them used in actual software, only in the classroom and in research papers. You will get a much better response at the Computer Science SE site than you will here. – user22815 Jul 10 '15 at 16:37
  • 2
    Yes, there is some overlap, but I am telling you as a veteran user of this site who is familiar with many of the tech/CS sites that this question will get the best responses at CS.SE. – user22815 Jul 10 '15 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.