Estimate the given sum.

Question

This is the question from "Data Structures and Algorithm Analysis in C" By Mark Weiss. It is the question 1.7. It goes as follows:-

Estimate the sum $\sum\limits_{i=\lfloor{N/2}\rfloor}^N\frac{1}{i}$.

My approach is as follows:-

$\sum\limits_{i=\lfloor{N/2}\rfloor}^N\frac{1}{i}$ = $\sum\limits_{i=1}^N\frac{1}{i} - \sum\limits_{i=1}^{\lfloor{N/2}\rfloor-1}\frac{1}{i}$ $\approx$ $\ln N - ln ({\lfloor{N/2}\rfloor-1})$.

After this I am lost. Any help please.

Answer 1

I asumme you are interested in asymptotic behavior of the series.

For large $N$, $$\ln(\lfloor N/2 \rfloor - 1) \sim \ln(N/2) = \ln(N) - \ln(2)$$

Hence, your series asymptotically tends to $\ln(2)$.

In general, $$\sum_{k = \lfloor N/\alpha \rfloor}^N \dfrac1k \underset{N \to \infty}{\to} \log (\alpha)$$ by the same argument.