# Master theorem: $T(n)=10T(n/9)+n\lg(n)$

I am told to solve the recurrence $$T(n)=10T(n/9)+n\lg(n)$$ using the Master theorem. I then try to use case 3. However, I am unable to show that for $$f(n)=n\lg(n)$$ then $$10f(n/9) \leq cn\lg(n)$$ for $$c < 1$$ and all sufficiently large $$n$$. Is it wrong to use case 3? Or does the Master theorem even apply?

• You should state the exat version of the master theorem you are using, there is a raft of them. – vonbrand Feb 19 at 21:19

Case 3 does not apply. Indeed: $$f(n) = n \log n \not\in \Omega(n^{\log_9 10}) = \Omega(n^{\log_b a}).$$
However case $$1$$ applies since, for $$0 $$f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log_9 10 - 0.01} ) \subseteq O(n^{\log_b a - c} ).$$
This shows that $$T(n) \in \Theta(n^{\log_9 10})$$.