How do we get this result?

Question

How do we get to the result that $$n\sum_{i=1}^{\log(n)} \frac{1}{i} =\Theta(n\log(\log(n)))$$?

Answer 1

As the function $1/x$ is monotonous, one establishes the following inequalities:

$$\sum_{i=1}^{\lfloor\log n\rfloor-1}\frac1{i+1}<\sum_{i=1}^{\lfloor\log n\rfloor-1}\int_i^{i+1}\frac{dx}x<\sum_{i=1}^{\lfloor\log n\rfloor-1}\frac1{i}$$

or

$$\sum_{i=1}^{\lfloor\log n\rfloor}\frac1i-1<\log\lfloor\log n\rfloor<\sum_{i=1}^{\lfloor\log n\rfloor}\frac1{i}-\frac1{\lfloor\log n\rfloor}.$$

Hence,

$$\log\lfloor\log n\rfloor+\frac1{\lfloor\log n\rfloor}<\sum_{i=1}^{\lfloor\log n\rfloor}\frac1i<\log\lfloor\log n\rfloor+1.$$

(The floor may be replaced by a ceiling.)

Answer 2

The sum $\sum_{i = 1}^\infty \frac{1}{i}$ is called the Harmonic series. One can show that $\sum_{i = 1}^k \frac{1}{i} = \Theta(\log(k))$. (Calculate this yourself using the integral of $\frac{1}{x}$.)

Can you now show that your result follows?