Proving f(n) = O(log n) with Induction

[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?

Thanks in advance.

 

[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..

 

[EvLer]

Thanks for reply.
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.