Q:

How to solve T(n)=T(n-1)+ (n-1) by Iteration Method?

Please can anyone help me with this:
Solve using iteration Method T (n) = T (n - 1) + (n - 1)
And prove that T (n) ∈Θ (n²)
Please, if you can explain step by step I would be grateful.

A:

I solved an easy way :
T (n) = T (n - 1) + (n - 1)-----------(1)
//now submit T(n-1)=t(n)

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

now submit (2) in (1) you will get
i.e T(n)=[T(n-2)+n-2]+(n-1)
T(n)=T(n-2)+2n-3 //simplified--------------(3)

now, T(n-2)=t(n)
 T(n-2)=T((n-2)-2)+[2(n-2)-3]
T(n-2)=T(n-4)+2n-7---------------(4)
now submit (4) in (2) you will get
i.e T(n)=[T(n-4)+2n-7]+(2n-3)
T(n)=T(n-4)+4n-10 //simplified
............
T(n)=T(n-k)+kn-10

now, assume k=n-1

T(n)=T(n-(n-1))+(n-1)n-10
T(n)=T(1)+n^2-n-10
According to the complexity 10 is constant

So , Finally O(n^2)

A:

T(n) = T(n - 1) + (n - 1)
      = (T(n - 2) + (n - 2)) + (n - 1)
      = (T(n - 3) + (n - 3)) + (n - 2) + (n - 1)
      = ...
      = T(0) + 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1)
      = C + n * (n - 1) / 2
      = O(n2)

Hence for sufficient large n, we have:

n * (n - 1) / 3 ≤  T(n) ≤ n2

Therefore we have T(n) = Ω(n²) and T(n) = O(n²), thus T(n) = Θ (n²).

