I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem. At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But then someone pointed out that $f(n)=nlogn$ and $n^{\log_3 9}$ do not have polynomial difference  and therefore master theorem cannot be used.Then I found this proof for master theorem. Proof of case 1 is on page 2 of the document right on top of the page. The proof is based on the inequality: $f(\frac{n}{b^i}) \leq(\frac{n}{b^i})^{\log_a b -\epsilon}$ which allows the right side of the above inequality to replace f(n) and the proof goes on from there.As I see it, the above inequality holds for $f(n)=nlogn$ so I think master theorem can be applicable here. I want to know if I am right and if not, why?
Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn
asymptotics;recurrence relation;master theorem
Citing CLRS 3ed pp. 94-95:In the first case, not only must $f(n)$ be smaller than $n^{\log_b a}$, it must be polynomially smaller. That is, $f(n)$ must be asymptotically smaller than $n^{\log_b a}$ by a factor of $n^\epsilon$ for some constant $\epsilon > 0$.Note that the three cases do not cover all the possibilities for $f(n)$. There is a gap between cases 1 and 2 when $f(n)$ is smaller than $n^{\log_b a}$ but not polynomially smaller.For your case we have:$$\begin{align}f(n) & = n \log n\\n^{\log_b a} & = n^2\\\end{align}$$We can then show:$$\begin{align}f(n) & = n \log n\\& < n^{2-\epsilon} & ^{*}\text{for } \epsilon < 1\\& < n^2 & \text{for } \epsilon > 0\\\end{align}$$Then you see we can pick a $\epsilon$ value in the range $(0, 1)$ to get a polynomial difference of at least $n^\epsilon$ because:$$ f(n) < n^{2-\epsilon} < n^2$$So yes, it is admissible, but your caution is noteworthy, because there are cases where the Master Theorem can not be applied in scenarios similar to this. One example would be the following:$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$You see $\frac{n}{\log n}$, while smaller than $n$, is not polynomially smaller, thus we cannot use the Master Theorem.$^*$: A polylogarithmic function grows more slowly than any positive exponent