0
$\begingroup$

Consider the following recursion: $\begin{cases} T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} &n > 1 \\ O(1) &n = 1 \end{cases}$.

The master theorem doesn't work, as the exponent of $\log n$ is negative. So I tried unfolding the relation and finally got the equation: $T(n) = n[1 + \frac{1}{\log(\frac{n}{2})} + \frac{1}{\log(\frac{n}{4})} + ... + \frac{1}{\log(2)}]$.

I do not know how to simplify (inequalities to use???) from here. A trivial method would be to assume that all reciprocal of the log terms are $< \frac{1}{\log(2)}$, and since there are $\log n$ terms, the summation of all the reciprocal-log terms is $< \frac{\log n }{\log(2)} = \log_2 n$, which gives $T(n) = O(n \log n)$. However this is a very poor approximation, as by the master theorem we can check that the time complexity for the recursive relation $T(n) = 2T(\frac{n}{2}) + n$ is $O(n \log n)$. Can someone find a tighter correct upper bound?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Check the Wikipedia page. $\endgroup$ – Yuval Filmus Sep 6 '19 at 21:52
  • 1
    $\begingroup$ Note that it's the master theorem (like a master key), not Master's theorem (named after some Professor Master). $\endgroup$ – David Richerby Sep 7 '19 at 9:11
1
$\begingroup$

Wikipedia has a slight extension of the master theorem which covers your case: case 2b here. For the recurrence $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log_b a}/\log n)$, it gives $T(n)=n^{\log_b a}\log\log n$.

Improve this answer
$\endgroup$

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