Asymptotic notation of sum 1 / i

Question

What is the asymptotic notation of

i.e.

sum_(i = 1)^n (1 / i)

First of all, this is not a homework. Second, since there is no formula to calculate fraction, I don't know how to express this summation with n and get the asymptotic notation.

That might be Theta(n), but I am not sure.

Answer 1

Your expression

sum_(i = 1)^n (1 / i)

is the n-th harmonic number.

From the Wikipedia article:

The n-th harmonic number is about as large as the natural logarithm of n. The reason is that the sum is approximated by the integral:

int_1^n (1 / x) dx

whose value is ln(n).

They also give this nice image which shows the correlation:

So it is Theta(log n).

See Finding Big O of the Harmonic Series or Simple proof of showing the Harmonic number Hn=Θ(logn) for details of the proof, it is quite simple.