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...