Solve the Recurrence : $T(n)=3T(n/3) +\frac{n}{\log(n)}$.

Question

This question has been asked before but doesn't solve my doubt.

After Solving the recurrence relation $$ T(n) = 3T(n/3) + \frac{n}{\log{n}}$$ I get following equation $$ T(n)=3^kT(n/3^k) + \frac{n}{\log{n}} +\frac{n}{log{\frac{n}{3}}} +\frac{n}{log{\frac{n}{3^2}}} \space\space\ldots \frac{n}{log{\frac{n}{3^k}}} $$

I don't understand how $$ \sum\frac{n}{log{\frac{n}{3^k}}}$$ beats $$3^k$$ asymptotically.

I don't know how to simplify the summation: $$ \sum\frac{n}{log{\frac{n}{3^k}}}$$

It would be great if you could provide a complete solution.

Answer 1

Using master theorem case 2b, as $\frac{n}{\log(n)} = \Theta(n\log^{-1}(n))$ ($c_{crit} = 1$ and $k = -1$), we have $T(n) = \Theta(n\log\log(n))$.

To know more, you can find this paper useful.