Using master theorem to solve recurrence with log 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.$$
Clearly $c := \log_3 4 &gt; 1$. Choose $1 &lt; d &lt; c$ arbitrarily, say $d = \frac{1+c}{2}$. Then $O(n\log n) = O(n^d)$ and $d &lt; \log_3 4$, and so we can apply the first case of the master theorem.