Estimate the given sum.

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.

-
$\ln\lfloor N/2\rfloor \approx \ln (N/2) = \ln N - \ln 2$, perhaps. –  mrf Jan 9 '13 at 21:19

1 Answer

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.

-
Thanks for the help. I just didn't consider the asymptotic behavior ( even though I was considering large values of N ). –  kusur Jan 9 '13 at 21:24