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

1. Jul 7, 2017

mikeng

This is probably really easy, but i am really rusty and i want to really understand.
I am trying to understand why $$log(n) < n^a$$ 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. Jul 7, 2017

Math_QED

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

3. Jul 7, 2017

mikeng

Thanks, that makes sense :)

4. Jul 7, 2017

mikeng

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 $$x^a < log(x)$$
Hmm but using derivatives then we must show that
1/x < a*x^(a-1)
Or is my thinking wrong?
Or more simpler that $$1< a*x^a$$

5. Jul 7, 2017

jbriggs444

Try n = 100, a = .001

6. Jul 7, 2017

7. Jul 7, 2017

mikeng

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
8. Jul 7, 2017

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.

9. Jul 7, 2017

mikeng

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 :)