CODEWITHSUNDEEP
algorithmasymptotic-complexitymaster-theorem
pratik watwani
pratik watwani

Reputation: 137

Algorithms : Master Theorem

Master theorem can be used to solve recurrence relations like T(n)= aT(n/b)+f(n).

So, if f(n)=O(n) or if f(n)=cn are both the values same? can I use master theorem for f(n)=cn also?

Upvotes: 3

Views: 355

Answers (2)

Codor
Codor

Reputation: 17605

If I understood the question correctly, f(n)=cn (where c is a constant) is in O(n); the master theorem can be applied.

Upvotes: 2

mort
mort

Reputation: 13588

Asumming that c is a constant and that I understand your question correctly, the solution will be the same for both f(n) = O(n) and f(n) = cn, since cn = O(n) and thus the Master theorem can be applied to solve the recurrance.

Upvotes: 3

Related Questions