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?
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:


If $f(n) = O(n^c)$ for $c &lt; \log_b a$ then $T(n) = \Theta(n^{\log_b a})$.
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)$.
If $f(n) = \Omega(n^c)$ for $c &gt; \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 &lt; 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$:


If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k &gt; - 1$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
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)$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k &lt; - 1$ then $T(n) = \Theta(n^{\log_b a})$.




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


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


In the first recurrence, $f(n) = \Omega(n^1)$, where $1 &gt; \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)$.