Solving using the master theorem [duplicate]

Question

I am wondering why this

$T(n)=3T(n/4)+n⋅lg(n)$

recurrence can be solve by Master Theorem case 3 but this
$T(n)=2T(n/2)+n⋅lg(n)$
recurrence can not be solve by Master Theorem what is the difference between this two recurrences.
When I searched on google I found tow questions related with this two recurrence
First Question:
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
Second Question:
T(n)=2T(n/2)+nlognT(n)=2T(n/2)+nlog⁡n and the Master theorem

But both of them say something in contrast with each other and I could't find out the main reason.

Answer 1

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

1. $f(n) = \Omega(n^c)$ for some $c > \log_b a$ (i.e. $b^c > a$), and
2. $af(n/b) \leq (1-\epsilon) f(n)$ for some $\epsilon > 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 > \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 > \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 > 0$.

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