How to solve this harmonic progression ? summation $\sum _{i=1} ^{\log(n)-1} \frac 1 {\log(n)-i}$?

Question

This question was actually derived from a time complexity recurrence relation question. Please also explain how is this a harmonic series.?$$\frac 1{\log (n)- i}$$ Explain how is this a harmonic series and is equal to loglogn

Answer 1

Presumably you meant $$ \sum_{i=1}^{\lfloor \log n \rfloor - 1} \frac{1}{\log n - i}$$

That is not a harmonic series, and is not $\log \log n$. However:

Let $\log n = m + r$ where $m = \lfloor \log n \rfloor$ and $0 \le r < 1$. Thus your sum is $$ S(n) = \sum_{i=1}^{m-1} \frac{1}{r + m - i}$$

Change variables to $j = m-i$, so $$ S(n) = \sum_{j=1}^{m-1} \frac{1}{r + j}$$ We have $$ \sum_{j=1}^{m-1} \frac{1}{j} \ge S(n) > \sum_{j=1}^{m-1} \frac{1}{1+j}= -1 + \sum_{j=1}^{m} \frac{1}{j}$$ so your sum is almost a partial sum of the harmonic series. From the standard asymptotics for those partial sums, $S(n) = \log m + O(1) = \log \log n + O(1)$.