Works at Amazon (company) · 10y ·
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
40.5K views ·
View upvotes
· 1 of 7 answers
Something went wrong. Wait a moment and try again.