Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold: 


  $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon &gt; 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c &lt; 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$


Our recurrence is defined as $$T(n) = 3T(n/4) + n \log n.$$

By definition we have, $a = 3, b = 4, f(n) = n \log n$. 

We now need to show that $f(n)$ is polynomially larger than $n^{\log_b a}$. That is the "$f(n) = \Omega(n^{\log_b a + \epsilon})$" part from above. Defining $\epsilon \approx 0.2$ achieves this. The reason being that $\log_4 3 \approx 0.793$ and $f(n) = \Omega(n^{0.793 + \epsilon})$. 

We are left to show that $f(n)$ satisfies the regularity condition. That is the "$a f(n/b) \leq c f(n)$ for some constant $c &lt; 1$ and all sufficiently large $n$" part.

We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) \log (n/4).$$ All we did was take the "$n$" in $f(n)$ and plug in "$n/4$". 

To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k \log k$. Swapping $k$ with $n/4$ we have $$3(n/4) \log (n/4) \leq (3/4)n \log n = c f(n)$$ where $c = 3/4$.

This finishes our necessary requirements and we have that $T(n) = \Theta(n \log n)$.