Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Learn more about Collectives

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Learn more about Teams

If a*f(n/b) = c*f(n) for some constant c > 1 then T(n) = (n^log(b) a)

If a*f(n/b) = f(n) then T(n) = (f(n) log(b) n)

If a*f(n/b) = c*f(n) for some constant c < 1 then T(n) = (f(n))

But when f(n) = log n or n*log n , the value of c is dependent on value of n. How do I solve the recursive function using master's theorem?

Usually, f(n) must be polynomial for the master theorem to apply - it doesn't apply for all functions. However, there is a limited "fourth case" for the master theorem, which allows it to apply to polylogarithmic functions.

If f(n) = O(n ^{log _b a} log ^k n), then T(n) = O(n ^{log _b a} log ^k+1 n).

In other words, suppose you have T(n) = 2T (n/2) + n log n. f(n) isn't a polynomial, but f(n)=n log n, and k = 1. Therefore, T(n) = O(n log ² n)

See this handout for more information: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf

You might find these three cases from the Wikipedia article on the Master theorem a bit more useful:

Case 1: f(n) = Θ(n ^c ), where c < log _b a

Case 2: f(n) = Θ(n ^c log ^k n), where c = log _b a

Case 3: f(n) = Θ(n ^c ), where c > log _b a

Now there is no direct dependence on the choice of n anymore - all that matters is the long-term growth rate of f and how it relates to the constants a and b. Without seeing more specifics of the particular recurrence you're trying to solve, I can't offer any more specific advice.

Hope this helps!

So for a case where f(n) = log n and a!=b, it won't fit 2nd case as c and k would have to be 1, but it'll give the function n*log n. So how do I check where this function fits? Sorry for so many questions. – amir shadaab Mar 31, 2013 at 23:38 Note that log n is not Theta(n^c) for any constant c. The only possible case that works here is the middle one, which might work if you had that a = b. If a != b, then you cannot directly apply the Master theorem to solve the recurrence and will have to find an alternate approach. – templatetypedef Apr 1, 2013 at 0:34 The master theorem can't always be applied. If it doesn't work, you need to use a different approach. What specific recurrence are you trying to solve? – templatetypedef Apr 1, 2013 at 4:52

When f(n)=log(n), the Master theorem is not applicable. You should use the more generalized theorem, Akra–Bazzi .

In result, T(n)=O(n).

source .

Another way to find a more specific proof of this result is looking for the proof of the computational complexity of the "Optimal Sorted Matrix Search" algorithm.

Thanks for contributing an answer to Stack Overflow!

• Please be sure to answer the question . Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.
• Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers .