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?