# Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

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...

-
So, what is your question? –  Keneth Adrian Mar 5 '12 at 2:18
Exercise 4.6.2 is very challenging. I might need hints in order to be able to solve it. –  Jean-Victor Côté Mar 5 '12 at 19:20
Use recursion trees. Then forget the Master Theorem. –  JeffE Mar 5 '12 at 21:25