---

Solution

Given recurrence is:

$T(n)=3T\left(\frac{n}{4}\right)+n\log n$

Compare with Master Theorem:

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$

Here,

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

Now,

$n^{\log_b a}=n^{\log_4 3}$

Since,

$\log_4 3<1$

So,

$n^{\log_4 3}<n$

But,

$f(n)=n\log n$

Clearly,

$n\log n$ grows faster than $n^{\log_4 3}$.

So, by Master Theorem Case 3,

$T(n)=\theta(n\log n)$