Easy: Solve T(n)=T(n-1)+n by Iteration Method

Question

Can someone please help me with this ?

Use iteration method to solve it. T(n) = T(n-1) +n

Explanation of steps would be greatly appreciated.

Answer 1

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

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

T(n-2) = T(n-3) + n-2

and so on you can substitute the value of T(n-1) and T(n-2) in T(n) to get a general idea of the pattern.

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

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

T(n) = T(n-k) + kn - k(k-1)/2    ...(1)

For base case:

n - k = 1 so we can get T(1)

=> k = n - 1
substitute in (1)

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

Which you can see is of Order n² => O(n²).

Answer 2

Expand it!

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

and so on, until

T(n) = 1 + 2 + ... + n = n(n+1)/2   [= O(n^2)]

provided that T(1) = 1