Master's theorem with f(n)=log n

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_ba log^k n), then T(n) = O(n^log_ba 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!