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 ?$$
Master Theorem Case 3 Regularity Condition
algorithms;master theorem
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)$.