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?

Question

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.

Answer 1

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)$.