O() proof?

1. Oct 30, 2004

EvLer

How can I show that function defined as

f(n) = f(n-1) + 1/n is O(logn) ?

Do I need to use induction here?

2. Oct 30, 2004

arildno

Note that, by induction, you have:
$$f(n)=a_{0}+\sum_{i=1}^{n}\frac{1}{i}$$
where $$a_{0}$$ is some constant.
Now, you need to find "how fast" the harmonic series grows..

Last edited: Oct 30, 2004
3. Oct 30, 2004