1
$\begingroup$

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?

$\endgroup$
  • $\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 '16 at 5:10
  • $\begingroup$ This recurrence also appeared at this MSE link. $\endgroup$ – Marko Riedel Jan 3 '16 at 19:43
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.