Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: O() proof?

  1. Oct 30, 2004 #1
    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.
  2. jcsd
  3. Oct 30, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Note that, by induction, you have:
    where [tex]a_{0}[/tex] is some constant.
    Now, you need to find "how fast" the harmonic series grows..
    Last edited: Oct 30, 2004
  4. Oct 30, 2004 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook