algorithm - How to solve: T(n) = T(n - 1) + n

Question

I have the following worked out:

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

Now when I work this out I find that the bound is very loose. Have I done something wrong or is it just that way?

Answer 1

You need also a base case for your recurrence relation.

T(1) = c
T(n) = T(n-1) + n

To solve this, you can first guess a solution and then prove it works using induction.

T(n) = (n + 1) * n / 2 + c - 1

First the base case. When n = 1 this gives c as required.

For other n:

  T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n

So the solution works.

To get the guess in the first place, notice that your recurrence relationship generates the triangular numbers when c = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

Intuitively a triangle is roughly half of a square, and in Big-O notation the constants can be ignored so O(n^2) is the expected result.