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 ?$$


1 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.