# Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure that the result is not just Big Oh, but also Big Theta and he informed me that I could have applied the Master Theorem to this recurrence relation. I however do not see how it applies. Below is images of the pdf of my current solution.

Could someone either verify that my solution is valid and point me in a direction of how I can assure that my solution is a tight bound or explain the application of the master theorem in this case to me?

• What's the obstruction to the Master Theorem here? It looks like Case 2 to me, but it's been a long time since I knew what big-theta notation meant. Nov 6, 2013 at 5:51
• @zibadawatimmy It cannot be case 2 as it would be necessary for $log_b a = 1$ as in $f(n) = n^c \lg n$, $c = 1$. This however is not the case as $$\log_b a = \log_4 6 > 1 = c,$$ so it falls into either case 1 or case 3.
– Alex
Nov 6, 2013 at 5:57
• If $n = 4^m$ then $$T(n) \sim n^{\log_4 6} (T(1)+6\log 4).$$ Perhaps the proof of Case 2 of the master theorem can be modified to suit this particular recurrence? Nov 6, 2013 at 17:15