Master Theorem Case 3 Regularity Condition

Question

In case 3 of the master theorem, we have to show that

$$ af(n/b) \leq cf(n). $$

I don't understand how I can setup this formula. As an example, we have

$$ T(n)=3T(n/4) + n \lg n.$$

In this case $a=3$ and $b=4$. This gives us $O(n^{0.793})$ which is smaller than $f(n) = n \lg n$ which means case 3.

Now, the solution is:

$$af(n/b)= 3(n/4) \lg(n/4) \leq (3/4)n\lg n.$$

I'm not sure how we got the above? $af(n/b)$ in my book is $3(n/4)$ so where does $\lg(n/4)$ come from? Also, since $f(n)$ is $n \lg n$, shouldn't the evaluation be:

$$3(n/4) \leq n \lg n ?$$

Answer 1

If $f(n) = n\lg n$ then $f(n/b) = (n/b)\lg(n/b)$, and so $af(n/b) = a(n/b)\lg(n/b)$.