The given recurrence is of the form:
T(n)=aT(n-b)+f(n), n>1 for some constants c,a>0,b>0,k>=0 and function f(n) and could be solved using Subtract and Conquer Recurrence method.
If f(n) is of the form n^k then,
T(n)={O(n^k), if a<1
O(n^(k+1)),if a=1
O(n^ka^(n/b)), if a >1}

Now to your question,
T(n)=T(n-1)+n
Comparing it with the general recurrence relation mention above we get
a=1, b=1,k=1 (since f(n) = n^1)
Since a=1, so from above T(n)= O(n^(k+1)), subtitute the value of k and we'll get our answer
T(n)=O(n^2).
Easy peasy with this approach. :D

View 6 other answers to this question
About · Careers · Privacy · Terms · Contact · Languages · Your Ad Choices · Press ·
© Quora, Inc. 2025