Understanding the Relationship Between Logarithmic and Exponential Functions

[mikeng]

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.

 

[member 587159]

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.

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

 

[mikeng]

Functions that satisfy ##x < y \Rightarrow g(x) < g(y)## are called increasing functions.

Thanks, that makes sense :)

 

[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 [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]

 

[jbriggs444]

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.

Try n = 100, a = .001

 

[mikeng]

Try n = 100, a = .001

Thanks, but then i must have misunderstood the origin of the question, it says. recall that for any c > 0, log(n) is O(n^c ).
This is the first problem from here https://ocw.mit.edu/courses/electri...fall-2011/assignments/MIT6_006F11_ps1_sol.pdf

There must be something i am missing here, cause clearly this is not true for all c> 0

 

[mikeng]

Thanks, but then i must have misunderstood the origin of the question, it says. recall that for any c > 0, log(n) is O(n^c ).
This is the first problem from here https://ocw.mit.edu/courses/electri...fall-2011/assignments/MIT6_006F11_ps1_sol.pdf

There must be something i am missing here, cause clearly this is not true for all c> 0

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.

 

[mfb]

The constant is the important difference. log(n) can be larger than n^a, 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.

 

[mikeng]

The constant is the important difference. log(n) can be larger than n^a, 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.

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