Solving using the master theorem
In these cases it's always a good idea to look at the statement of the master theorem. The statement on Wikipedia states regarding case 3 that if
$T(n) = aT(n/b) + f(n)$ where


$f(n) = \Omega(n^c)$ for some $c &gt; \log_b a$ (i.e. $b^c &gt; a$), and
$af(n/b) \leq (1-\epsilon) f(n)$ for some $\epsilon &gt; 0$ and large enough $n$,


then $T(n) = \Theta(f(n))$.

Let's see whether the theorem applies in your two cases. In your first case $a = 3$, $b = 4$, and $f(n) = n\log n$. We have $f(n) = \Omega(n^1)$ and $1 &gt; \log_4 3$, and furthermore $$3f(n/4) = 3(n/4)\log(n/4) \leq (3/4)n\log n = (3/4)f(n).$$
Both conditions are satisfied, and so we can conclude that $T(n) = \Theta(n\log n)$.

In your second case $a = b = 2$ and $f(n) = n\log n$ is the same. In this case $f(n) = \Omega(n^c)$ only for $c \leq 1$, whereas we need $c &gt; \log_2 2 = 1$, so we cannot apply case 3. The second condition also doesn't hold, since $2f(n/2) = 2(n/2)\log(n/2) = n\log n - \Theta(n)$, and so it is not true that $2f(n/2) \leq (1-\epsilon) f(n)$ for any $\epsilon &gt; 0$.

However, in this example case 2 of the master theorem applies, showing that $T(n) = \Theta(n\log^2 n)$.