If f(n) contains some term of log(n), is it possible to solve this by the Master Method?

Question

The Master Method is a direct way to get the solution. The Master Method works only for following type of recurrences or for recurrences that can be transformed to following type.

T(n) = a T(n / b) + f(n) where a ≥ 1, b > 1, and f(n) = Θ(n^c).

There are following three cases:

1. If c < log_b(a) then T(n) = Θ(n^log_b(a)).

2. If c = log_b(a) then T(n) = Θ(n^c log(n)).

3. If c > log_b(a) then T(n) = Θ(f(n)).

In the Master Method, if f(n) contains some term of log(n), is it possible to solve this by the Master Method? for example in T(n)=4T(n/2)+n^2logn Here master's theorem appplicable or not

Answer 1

It is not really possible to tell directly whether or not the Master Method works for some logarithmic function. This would depend on the specific recurrence you're trying to solve. It all depends on how f grows in comparison to n^{log_b a}.

In the example given by JPC (where T(n) = 4T(n/2) + log(n)), it is indeed possible. However, also consider the example T(n) = 2T(n/5) + log(n). In this recurrence it is harder to determine whether n^{log₅ 2} grows faster than log(n). If the logarithmic function f(n) gets more complex (e.g. log₃(n/2)), it becomes even harder.

In short, it may be hard to determine for logarithmic functions how they grow when compared to an exponential function when the exponent is less than 1 (for exponents >= 1, log(n) is always faster). If it doesn't seem to work for you, you'll have to use other techniques to solve the recurrence.