Solve the following Recurrence using any method just help in solving

Question

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

Comments

$O(n^2)$
https://stackoverflow.com/questions/13674719/easy-solve-tn-tn-1n-by-iteration-method

Answer 1

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

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

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

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

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

Now substituting (2) in (1)

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

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

Now substituting (4) in (0)

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

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

           ...

           ...

T(n)=T(n-k)+kn-k

​​​​​​​put k=n-1 in above equation

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

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

∴ The solution is O(n^2)

Comments

how the O(n^2) will come

---

take the largest term from the equation