# Solving recursion $T(n)=2T(n/2) +2/\log(n)$

everybody, I'm trying a whole day to compute this recursion. I will be grateful if someone can try and solve it

$$T(n)=2*T(n/2)+2/\log(n),$$

where $\log n$ is the logarithm to the base 2 - of course! thanks!

Writing the recursion, we have:

\begin{align} T(n)&=2T(n/2)+2/\lg n\\& = 2(2T(n/4)+2/\lg(n/2))+2/\lg n\\& = 4T(n/4)+4/(\lg n-1)+2/\lg n\\& = 4(2T(n/8)+2/\lg(n/4))+4/(\lg n-1)+2/\lg n\\& = 8T(n/8)+8/(\lg n - 2)+4/(\lg n-1)+2/\lg n\\& \;\,\vdots\\& = 2^kT(n/2^k)+\sum_{i=1}^k\frac{2^i}{\lg n - i + 1},\\& \end{align} replacing $k$ with $\lg n$, we found:

$$T(n)=nT(1)+\sum_{i=1}^{\lg n}\frac{2^i}{\lg n - i + 1}.$$

As mentionned in the comments, by choosing $j=\lg n - i + 1$ in the summation ($i = \lg n - j + 1$), we obtain:

\begin{align}T(n)&=nT(1)+\sum_{j=\lg n}^{1}\frac{2^{\lg n - j + 1}}{j}\\&=nT(1)+\sum_{j=1}^{\lg n}\frac{2n}{j2^j}\\&=nT(1)+2n\sum_{j=1}^{\lg n}\frac{1}{j2^j}\\&=n\Bigl(T(1)+2\sum_{j=1}^{\lg n}\frac{1}{j2^j}\Bigr).\end{align}

We finally obtain $$T(n)=\Theta(n).$$

• Note: the sum in the final equation $\le 2n$. – Reinstate Monica Aug 15 '18 at 16:27
• It's better to switch the summation to $j = \lg n - i + 1$, in which case we're summing $2n/(j2^j)$ from $j = 1$ to $j = \lg n$, which makes it clear that $T(n) = \Theta(n)$. – Yuval Filmus Aug 15 '18 at 18:57