# 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

### EvLer

Would it be right to describe it as:
for n0 > 2, c = 1, then f(n) < c * g(n) ?
Looking at the graphs, or rather how the harmonic series behaves compared to the graph of logn, it is kind of obvious that logn is the upper bound.
Thanks again.