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


    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


    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 by a moderator: Jul 7, 2017
  9. Jul 7, 2017 #8


    User Avatar
    2017 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 :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted