6
$\begingroup$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is asymptotically larger than n, it is not polynomially larger because the ratio $\tfrac{n\lg n}{n}=\lg n$ is asymptotically less than $n^{\epsilon}$ for any positive constant $\epsilon$. Consequently, the recurrence falls into the gap between case 2 and case 3." For a solution, the authors send us to exercise 4.6.2 on page 106:

"Show that if $f\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k}n\right)$, where $k\geq0$, then the master recurrence has solution $T\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k+1}n\right)$. For simplicity, confine your analysis to exact powers of b."

(Here $\lg^k n$ is CLRS's notation for $(\log_2 n)^k$.)

This is where I am starting to have problems...

  • 0
    So, what is your question?2012-03-05
  • 0
    Exercise 4.6.2 is very challenging. I might need hints in order to be able to solve it.2012-03-05
  • 0
    Use [recursion trees](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf). Then forget the Master Theorem.2012-03-05

2 Answers 2