1. Limited time only! Sign up for a free 30min personal 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!

I Help understand, log(n) < n^a

  1. Jul 7, 2017 #1
    This is probably really easy, but i am really rusty and i want to really understand.
    I am trying to understand why [tex] log(n) < n^a [/tex] For all n,a>0.
    I am really having a hard time to get an intuition over this, of course if i let a >= 1 then its obvious, but how do i know if there is not some extremely small epsilon that breaks the inequality. I understand maybe i should use that in a proof but i am kinda stuck.

    Also this is not really directly related but a thought i had, is there a name for functions that has the property that if x < y then g(x) < g(y), i'm curious.
     
  2. jcsd
  3. Jul 7, 2017 #2

    Math_QED

    User Avatar
    Homework Helper

    Functions that satisfy ##x < y \Rightarrow g(x) < g(y)## are called increasing functions. You might want to read this: https://en.wikipedia.org/wiki/Monotonic_function
     
  4. Jul 7, 2017 #3
    Thanks, that makes sense :)
     
  5. Jul 7, 2017 #4
    I see did not occur to me to use derivatives.
    I have been looking this over to try to see if i missed something but correct me if i am wrong but this does only show log(x) < x. But i wonder if there is a constant a such that [tex]x^a < log(x) [/tex]
    Hmm but using derivatives then we must show that
    1/x < a*x^(a-1)
    Or is my thinking wrong?
    Or more simpler that [tex]1< a*x^a [/tex]
     
  6. Jul 7, 2017 #5

    jbriggs444

    User Avatar
    Science Advisor

    Try n = 100, a = .001
     
  7. Jul 7, 2017 #6
  8. Jul 7, 2017 #7
    Hold on a minute lol i forgot the constant, i can choose my constant in the definition of big oh, to cancel any c>0, or?

    Well after thinking not sure how to find such a constant. Hmm i am prob making this allot more complicated.
     
    Last edited: Jul 7, 2017
  9. Jul 7, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The constant is the important difference. log(n) can be larger than na, but no matter which a you choose, it will always be at most some factor c larger (c depends on a). Finding a specific c can be challenging but it is not necessary. It is sufficient to show that such a c exists.
     
  10. Jul 7, 2017 #9
    Thanks it makes sense, will continue to think of how to prove that, to show that no matter how much bigger log(n) is then n^a, it is always bigger by some constant factor. But at least i understand why it is true, just want to prove it. Thanks :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Help understand, log(n) < n^a
Loading...