Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence
$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$
by applying the Master Theorem.
I am very confused by how it is done. So, $a=3, b=4, f(n) = n\cdot \log(n)$
First step is to compare $n^{\log_b a} = n^{\log_4 3}= O(n^{0.793})$ with $f(n)$.
I have no clue on how they compared this. The book explains:
$f(n) = \Omega (n^{\log_4 3+\epsilon })$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$
Followed by:
For sufficiently large n, we have that: $af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$
Where did $3\left(\frac{n}{4}\right)$ come from?