10
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ $\log n$ is not of the form $n^\epsilon$. Hence the need for a separate name, $\log$. $\endgroup$
    – lhf
    Oct 16, 2013 at 4:12
  • $\begingroup$ 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)$. $\endgroup$
    – Lucian
    Oct 16, 2013 at 9:54

3 Answers 3

10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This can be proved by considering derivatives. $\endgroup$
    – lhf
    Oct 16, 2013 at 4:19
  • $\begingroup$ Ah, I see. So it is more accurate to say $log(n) = O(n^\epsilon)$ where $\epsilon << 1$. $\endgroup$ Oct 16, 2013 at 4:23
  • $\begingroup$ @lhf Or just by considering the values at 1. $\endgroup$ Oct 16, 2013 at 4:23
  • $\begingroup$ @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$. $\endgroup$ Oct 16, 2013 at 4:26
  • 1
    $\begingroup$ @mLstudent33 Here is the definition of the $O(\ldots)$ notation that OP and I are using: en.wikipedia.org/wiki/Big_O_notation $\endgroup$ May 17, 2020 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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