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?

  • $\begingroup$ The sum evaluates to T(n) = $2n. \sum_{k=1}^{log_2n}\frac{1}{log_2\frac{n}{2^k}}$ $\endgroup$
    – Cloverr
    Jan 3, 2016 at 5:10
  • $\begingroup$ This recurrence also appeared at this MSE link. $\endgroup$ Jan 3, 2016 at 19:43

1 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))$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.