How to the examples for using the master theorem in Cormen work?

ignougroup
Problem Detail: I’m reading Cormen’s Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples

  1. $3T( frac{n}{4} ) + nlog(n)$
  2. $2T( frac{n}{2} ) + nlog(n)$

For the first example we have $a=3$ and $b=4$ so $n^{log_4 (3)}=n^{0.793}$ and Cormen says that if we choose $epsilon = 0.207$ then $f(n) = nlog(n) = Omega(n^{log_4(3) + epsilon})$ How? As I understand it if $epsilon = 0.207$ then $Omega(n^{log_4(3) + epsilon})= Omega(n)$ so we have $nlog(n) = Omega(n)$ but it’s not true; But he proves that $nlog(n) = Omega( n^{log_4(3) + epsilon} )$ And then he proves that for the second case $nlog(n)$ does not apply to masters method 3-rd case the same way as I prove above. So could somebody explain me in detail how the third case of the master’s theorem applies to $3T( frac{n}{4} ) + n log(n)$ but not to $2T( frac{n}{2} ) + nlog(n)$.

Asked By : Vahagn Babajanyan

Answered By : Reza

I think you used that method wrong! As mentioned in master theorem case 3. In your case you should use case 3 which uses $Omega$-notation which describes asymptotic lower bound. So the solution in the book is correct! You used $O$-notations which is and asymptotic upper bound! Be careful about which cases in master theorem you are using! To satisfy the second case you should also have $af(n/b) leq cf(n)$ for some $c < 1$ and large $n$. In your case, $f(n) = n log(n)$. $a=3$, $b=4$ you should show that $qquad 3(n/4 cdot log(n/4)) leq c n log(n)$. For large $n$ you could select $1 geq c geq 0.75$ which solves your equation.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9390