This question already has an answer here:

I'm not sure how to solve apply the master theorem in order to solve this recurrence:

$$ T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$

The master theorem I have been shown is normally used to solve recurrences of the slightly different form $$ T(n) = aT(n/b) +O(n^d),\text{ where }T(1) = 1.$$


marked as duplicate by David Richerby, Discrete lizard, Evil, Thomas Klimpel, Luke Mathieson Feb 12 at 23:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Wikipedia has a thorough article on the master theorem, which includes all you need to know in order to solve this question. $\endgroup$ – Yuval Filmus Feb 3 at 17:27
  • $\begingroup$ Our reference question (linked above) also deals with using the master theorem. $\endgroup$ – David Richerby Feb 3 at 17:28

Clearly $c := \log_3 4 > 1$. Choose $1 < d < c$ arbitrarily, say $d = \frac{1+c}{2}$. Then $O(n\log n) = O(n^d)$ and $d < \log_3 4$, and so we can apply the first case of the master theorem.

  • $\begingroup$ why does O(n log n) = O(n^d) ? Also thanks for the reply! $\endgroup$ – J.Doe Feb 3 at 17:39
  • $\begingroup$ I'll let you figure that out. $\endgroup$ – Yuval Filmus Feb 3 at 17:44

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