Using master theorem to solve recurrence with log
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.