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!

Simple function growth

  1. Mar 28, 2005 #1
    Show log n < O(n^epsilon) for n sufficiently large.

    Not actually calculus, but it has something to do with limits, so there. :rofl:

    Thanks,

    Mary
     
  2. jcsd
  3. Mar 28, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Did you try looking at

    [tex]\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon}[/tex]

    If you can evaluate this limit, the bound you're after follows.
     
  4. Mar 28, 2005 #3
    I know the limit is 0...but how do you evaluate it?
     
  5. Mar 28, 2005 #4
    The answer is quite intuitive...but i want a rigorous method
     
  6. Mar 28, 2005 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    l'hopital's rule will handle the limit.

    Are you able to convert from the limit to the big-O bound? This will follow from the definition of the limit.
     
  7. Mar 28, 2005 #6
    yes, but my instructor specifically mentioned not to use l'hopitals rule
     
  8. Mar 28, 2005 #7
    there is a pure algebra method
     
  9. Mar 28, 2005 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    If I write

    [tex]\log n=\frac{2}{\epsilon}\log n^\frac{\epsilon}{2}[/tex]

    does that help you evaluate the limit?
     
  10. Mar 28, 2005 #9
    log n^epsilon/2 has to grow slower than n^epsilon?
     
  11. Mar 28, 2005 #10
    oh...i see...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?