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

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?

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.

Think of it this way:
In each "iteration" of the recursion you do O(n) work.
Each iteration has n-1 work to do, until n = base case. (I'm assuming base case is O(n) work)
Therefore, assuming the base case is a constant independant of n, there are O(n) iterations of the recursion.
If you have n iterations of O(n) work each, O(n)*O(n) = O(n^2).
Your analysis is correct. If you'd like more info on this way of solving recursions, look into Recursion Trees. They are very intuitive compared to the other methods.

The solution is pretty easy for this one. You have to unroll the recursion:

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n 

You have arithmetic progression here and the sum is 1/2*n*(n-1). Technically you are missing the boundary condition here, but with any constant boundary condition you see that the recursion is O(n^2).