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


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

  • $\begingroup$ Note: the sum in the final equation $\le 2n$. $\endgroup$ – Reinstate Monica Aug 15 '18 at 16:27
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Aug 15 '18 at 18:57

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.