Asymptotic complexity T (n) = T (n-1) + 1 / n

Question

There is an algorithm with time complexity

T(n)=T(n-1)+1/n if n>1 =1 otherwise 

I solve its asymptotic complexity and get the order as "n", but the answer to this question is "log n". Is it correct? If it is log n, then why?

Answer 1

It is easy to see (or formally proved with induction) that T (n) is the sum 1 / k for values ​​of k from 1 to n. This is n th the number of harmonics , H _n = 1 + 1/2 + 1/3 + ... + 1 / n.

Asymptotically, harmonic numbers grow on the order of log (n). This is due to the fact that the sum is close in magnitude to the integral from 1 / x from 1 to n, which is equal to the natural logarithm of n. Indeed, H _n = ln (n) + γ + O (1 / n), where γ is a constant. From this it is easy to show that T (n) = Θ (log (n)).

Answer 2

More details:

C H(N) = 1 + 1/2 + 1/3 + ... + 1/N

function x :-> 1/x is a decreasing function, therefore:

We sum from 1 to N left side and for the right side we sum from 2 to N and add 1 , we get:

Then we calculate the left and right sides: ln(N+1) <= H(N) <= 1 + ln(N)

this means H(N)/ln(N) -> 1 , therefore, H(N)=Θ(log(N))

(from http://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique#.C3.89quivalent_de_Hn )