1

I want to calculate the summation $$\sum_{i=0}^{\log_2 n - 1}\frac{1}{\log_2 n-i}$$ when $n$ is a power of $2$.

Even a reasonable estimate on lower bound and upper bound on this summation is fine for me.

I know that we can establish the lower bound and upper bound using integration but I am not able to correctly establish what this bound will be.

dfeuer
  • 9,069
Subodh
  • 11
  • 2
    What do you mean by this sum? $\log n$ is not an integer. – dfeuer Sep 23 '13 at 23:48
  • Assuming that log n is an integer, how can we compute this summation. I am solving a recurrence relation where I am not able evaluate this summation to determine the time coplexity – Subodh Sep 23 '13 at 23:51
  • $\log n$ is never an integer. Do you mean $\lfloor \log n \rfloor$, the greatest integer less than or equal to $n$? – dfeuer Sep 23 '13 at 23:52
  • 1
    he may mean $\log_2$ or $\log_{10}$ – obataku Sep 23 '13 at 23:53
  • @oldrinb is right. I am sorry I should have made this clear. The logarithm base is 2. – Subodh Sep 24 '13 at 00:03

1 Answers1

3

Note for integer $m$ we have $$\sum_{k=0}^{m-1}\frac1{m-k}=\sum_{j=1}^m\frac1j=H_m\sim\ln m+\gamma,$$ where $H_m$ denotes the $m$th Harmonic number and $\gamma$ the Euler-Mascheroni constant.

dfeuer
  • 9,069
obataku
  • 5,571