Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry about asking such an elementary question, but I have been wondering about this exact definition for a while. What power of $n$ is $\log(n)$. I know that it is $n^\epsilon$ for a very small $\epsilon$, but what value is $\epsilon$ exactly?

share|improve this question
2  
$\log n$ is not of the form $n^\epsilon$. Hence the need for a separate name, $\log$. –  lhf Oct 16 '13 at 4:12
    
On one hand, no matter how small $\epsilon>0$ is, (say, one over a billion), as n grows towards infinity, it will inevitably reach a certain (large) value for which $n^\epsilon = \sqrt[1,000,000,000]n\ $ will become larger, believe it or not, the logarithmic function ! On the other hand, were $\epsilon$ to be exactly $0$ , we'd have $n^0=1$ be itself dwarfed by the logarithmic function, as the latter's value grows unhinged towards infinity. So there's simply no appropriate value of $\epsilon$ for which $n^\epsilon$ ultimately approximates or converges to that of $log(n)$. –  Lucian Oct 16 '13 at 9:54
add comment

3 Answers 3

up vote 5 down vote accepted

No: If $\epsilon$ is any positive number, then $n^{\epsilon}$ grows faster than $\log{n}$. This can be made precise in the statement

$$\lim_{n \to \infty} \frac{\log{n}}{n^{\epsilon}} = 0$$

for all $\epsilon > 0$. To prove this, just note that by L'Hospital's rule,

$$\lim_{n \to \infty} \frac{\log{n}}{n^{\epsilon}} = \lim_{n \to \infty} \frac{\frac{1}{n}}{\epsilon n^{\epsilon - 1}} = \frac{1}{\epsilon} \lim_{n \to \infty} \frac{1}{n^{\epsilon}} = 0$$

share|improve this answer
add comment

Suppose we seek such $\varepsilon$, that $$ n^\varepsilon = \log(n). $$ Consider $n>1$. Then (if $\log(n)$ is natural logarithm, to the base $e$) $$ n^\varepsilon = e^{\varepsilon\log(n)}, \qquad \log(n) = e^{\log(\log(n))}, $$ then powers of $e$ must be equal: $$ \varepsilon \log(n) = \log(\log(n)), $$ $$ \varepsilon = \frac{\log(\log(n))}{\log(n)}. $$

Examples:
$n=10$: $\varepsilon = 0.3622156886...$;
$n=10^2$: $\varepsilon = 0.3316228421...$;
$n=10^3$: $\varepsilon = 0.2797789811...$;

$n=10^6$: $\varepsilon = 0.1900611565...$;

$n=10^9$: $\varepsilon = 0.1462731331...$.

share|improve this answer
add comment

Perhaps T. Bongers has answered the question you meant to ask, but given your mention of the definition of $\log$ I'm not so sure. To answer your question literally, the function $n \mapsto \log(n)$ is not equal to the function $n \mapsto n^\epsilon$ for any number $\epsilon$ (not even if $\epsilon$ is "very small.) It is a different kind of function altogether, with very different properties, and it is certainly not defined as a power function.

share|improve this answer
    
This can be proved by considering derivatives. –  lhf Oct 16 '13 at 4:19
    
Ah, I see. So it is more accurate to say $log(n) = O(n^\epsilon)$ where $\epsilon << 1$. –  q2liu Oct 16 '13 at 4:23
    
@lhf Or just by considering the values at 1. –  Trevor Wilson Oct 16 '13 at 4:23
    
@q2liu It is accurate to say $\log(n) = O(n^\epsilon)$, or even $\log(n) = o(n^\epsilon)$, for every positive $\epsilon$. For any $\epsilon$, it would be wildly inaccurate to say that the function $\log(n)$ is defined as $n^\epsilon$, or that it is equal to $n^\epsilon$ for all $n$. –  Trevor Wilson Oct 16 '13 at 4:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.