Time complexity

Question

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

Can we apply master's theorem here ??

Comments

The generic form of master theorem.
T(n) = aT(n/b) + f(n)

So T(n)=T(n-1) + O(n) does not match the form. Can't apply the theorem

---

 Rajucse  for these type of question go with Back Substitution Method.

---

i know one more master method which used for this type of question ( subtract and conquer problems )

https://www.geeksforgeeks.org/master-theorem-subtract-conquer-recurrences/

but i encounter one example which this method fails.... i am searching that question, if i found i will post it here

---

This is new for me, can we trust on that Shaik sir. Because if there is even one example to which it fails it , means it is not a theorem.

Answer 1

No, you would be not able to apply the Master theorem here. As you can use the Master theorem under specific criteria I.e. the recurrance equation has to be like, T(n) = aT(n/b) + f(n).

If this not the case it's not possible. Also the a and b does not have to be the functions  as well.

If the recurrance relation contains the root operator then it is possible to apply the Master theorem.

Ex: T(n) = T(root(n)) + f(n)