# Recurrence relation (not solvable by the master theorem) [duplicate]

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?

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

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