1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Note that, by induction, you have:
    [tex]f(n)=a_{0}+\sum_{i=1}^{n}\frac{1}{i}[/tex]
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: O() proof?
  1. Proof for this (Replies: 2)

  2. Proof ! (Replies: 0)

  3. Physics :o (Replies: 1)

Loading...