# Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence

$$T(n)=3T(n/4) + n\log n$$

is solvable with Master Method but

$$T(n)=2T(n/2) + n\log n$$

isn't?

Despite they both look very similar except the values of coefficient '$$a$$' and size cutter '$$b$$'.

I understand that the work function '$$f(n)$$' must be polynomially larger/smaller than $$n^{\log_ba}$$. And that in second recurrence $$n^{\log_22}=n$$ is not polynomially comparable to $$f(n)=n\log n$$. So Master Method cannot be applied. But why can it be applied to the first recurrence?

I found these examples in CLRS Intro to Algo book, and can't understand them. Can you please explain.

Let us use the master theorem as stated on Wikipedia. Consider a recurrence $$T(n) = aT(n/b) + f(n).$$ There are several cases to consider:

1. If $$f(n) = O(n^c)$$ for $$c < \log_b a$$ then $$T(n) = \Theta(n^{\log_b a})$$.
2. If $$f(n) = \Theta(n^{\log_b a} \log^k n)$$ for $$k \geq 0$$ then $$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$$.
3. If $$f(n) = \Omega(n^c)$$ for $$c > \log_b a$$ and $$f(n)$$ is "reasonable" then $$T(n) = \Theta(f(n))$$.

In the third case, a function is "reasonable" if there exist $$k < 1$$ and $$N$$ such that for $$N \geq n$$, we have $$af(n/b) \leq kf(n)$$.

There are also extensions of the second case that handle all values of $$k$$:

1. If $$f(n) = \Theta(n^{\log_b a} \log^k n)$$ for $$k > - 1$$ then $$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$$.
2. If $$f(n) = \Theta(n^{\log_b a} \log^k n)$$ for $$k = - 1$$ then $$T(n) = \Theta(n^{\log_b a} \log\log n)$$.
3. If $$f(n) = \Theta(n^{\log_b a} \log^k n)$$ for $$k < - 1$$ then $$T(n) = \Theta(n^{\log_b a})$$.

Now back to your recurrences. The values of $$a,b$$ and $$f(n)$$ are:

1. $$a=3$$, $$b=4$$, $$f(n) = n\log n$$.
2. $$a=2$$, $$b=2$$, $$f(n) = n\log n$$.

In the first recurrence, $$f(n) = \Omega(n^1)$$, where $$1 > \log_4 3$$, and so, according to the third case of the master theorem, $$f(n) = \Theta(n\log n)$$ (you have to check that the function $$n\log n$$ is reasonable).

In the second recurrence, $$f(n) = \Theta(n^1 \log^1 n)$$, where $$1 = \log_2 2$$, and so, according to the second case of the master theorem, $$f(n) = \Theta(n\log^2 n)$$.