How can one solve $$T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log n$$ without using the master method?

I know it has a solution using the master theorem from this link.

| cite | improve this question | | | | |
  • $\begingroup$ Hello to cs.stackexchange site, you can use latex to write math equation. $\endgroup$ – jonaprieto May 4 '16 at 5:18
  • $\begingroup$ What's wrong with using the master theorem? Why tie one hand behind your back by refusing to use an appropriate tool? $\endgroup$ – David Richerby May 4 '16 at 8:12
  • $\begingroup$ @DavidRicherby I agree. Please convince my teacher. $\endgroup$ – eightShirt May 4 '16 at 17:25
  • 1
    $\begingroup$ @eightShirt Aaaaaaah, you're trying to get us to do your homework for you. Well, in that case, the point is to give you experience in using other techniques. That's a perfectly reasonable pedagogical tool but you won't learn anything from us applying other techniques for you. $\endgroup$ – David Richerby May 4 '16 at 17:38
  • $\begingroup$ @DavidRicherby He solve recurrences without master method. This recurrence is not a homework, just an exercise that I see here -cs.stackexchange.com/questions/3504/… I'm trying to understand, but with master method is easy to see is O(nlogn). $\endgroup$ – eightShirt May 4 '16 at 18:03


The master theorem is the result of observing the tree associated to the recursive relation $T(n)$. So, one possible way can be considering draw by yourself this tree, begin with the root, in this case, $n\log n$ and descending with three nodes, each one $T(n/4)$, and so on. When you see the pattern, look at each level of the tree, then sum up all nodes, and sum all levels, the total should give you an answer.

| cite | improve this answer | | | | |
  • $\begingroup$ Thanks. I found T(n) = 4nlogn - 24n + 25n^log4 3. So the complexity is O(n log n) $\endgroup$ – eightShirt May 10 '16 at 3:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.