Why can't this be done with Master Theorem

Question

Apparently recurrences like this cannot be solved with the Master Theorem:

$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$

Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) = \frac{n}{\log(n)}$ since $\frac{n}{\frac{n}{\log(n)}} = \log(n)$, which is less than $n^\epsilon$ for any positive $\epsilon$.

But when is this really even an issue?

For example why wouldn't the time complexity be $n \log n$ using case 2 of the Master Theorem? Unrolling the recursion:

$$T(n) = n\sum_{k=1}^{\log_2(n)} \frac{1}{\log_2(2^k)}$$

$$T(n) = n\sum_{k=1}^{\log_2(n)} \frac{1}{k}$$

Doesn't this suggest $\Theta(n \log n)$ even though it supposedly cannot be done with Master Theorem?

Answer 1

Letting $n=2^m$, we have $$T(n) = 2T\left(\dfrac{n}2\right) + \dfrac{n}{\log n}$$ Setting $g(k) = T(2^k)$, we have $$g(k) = 2g(k-1) + \dfrac{2^k}{k}$$ Hence, we have \begin{align} g(m) & = 2g(m-1) + \dfrac{2^m}m = 4g(m-2) + \dfrac{2^m}{m-1} + \dfrac{2^m}m\\ & = \sum_{k=1}^m \dfrac{2^m}k + 2^m g(0) \sim 2^m \log_e(m) \end{align} where the last step is true because $\sum_{k=1}^m \dfrac1k = \log_e(m) + \gamma + \mathcal{O}(1/n)$. Since $m=\log_2(n)$, we obtain $$T(n) \sim n\log_e(\log_2(n))$$