Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

Question

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?

Answer 1

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

Answer 2

You can apply the case one of master theorem

Case 1 : If $f(n) = \theta(n^c)$ where $c < log_ba$ then $T(n) = \theta(nlog_ba)$. According to the recurrence equation $\theta(n^{1+x})=nlogn$ where $1+x=c$ and $c<2$ because of the obvious reason $logn<n$ hence $c<log_ba$. And the result of the equation will be $\theta(n^2)$.