Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

Question

I am given an example of a case where the master theorem does not apply, but it seems like it should apply.

This was the reasoning:

$T(n) = 3T(n/3) + n \log n$ with $ a = 3, b=3, f(n) = n\log n$ and $n\log_b a = n\log_3 3 = n$

$f(n)$ is asymptotically larger than $n\log_b (a)$ , but not polynomially larger. The ratio $n \log n / n = \log n$ is asymptotically less than $n^\epsilon$ for any positive $\epsilon$. Thus, the Master Theorem doesn’t apply here

However, it seems like case 2 of the master theorem should apply here. We have $f(n) = n\log n$, and thus $f(n) = \theta(n^{\log_3 3} \log n$)

Then: $T(n) = \theta(n^{\log_a b} \log^{k+1}n) = \theta(n\log^2 n)$

Which is correct?

Answer 1

Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to consider case 3 of the Master Theorem since $f(n)=\Omega(n)$.

However, the theorem requires that there exist an $\epsilon > 0$ such that $n\;log\;n = \Omega(n^{1+\epsilon})$. Is this condition met? Equivalently, is it true that $log\;n = \Omega(n^{\epsilon})$ ? As long as $\epsilon$ is positive, this is never true. The polynomial will grow faster. Therefore, the Master Theorem does not apply. You could use iteration or some other method to solve the recurrence.

After searching around, I've found a few references to a corollary of the Master Theorem that addresses polylogarithmic functions. In this version, if we can show that $f(n)=\Theta(n^{log_ba}log^{k}n)$ for some $k \geq 0$, then we can conclude that $T(n) = \Theta(n^{log_ba}log^{k+1}n)$. In our case, $f(n) = \Theta(n\;log\;n)$ with $k=1.$ Therefore, we could conclude that $T(n)=\Theta(n\;log^{2}n)$. However, I don't think this is commonly referred to (or taught) as part of the Master Theorem.

Reference 1

Reference 2