# Using master theorem to solve recurrence with log [duplicate]

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 MathiesonFeb 12 at 23:48

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.