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?

enter image description here enter image description here

  • $\begingroup$ 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. $\endgroup$ Nov 6, 2013 at 5:51
  • $\begingroup$ @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. $\endgroup$
    – Alex
    Nov 6, 2013 at 5:57
  • $\begingroup$ 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? $\endgroup$ Nov 6, 2013 at 17:15


You must log in to answer this question.

Browse other questions tagged .