0
$\begingroup$

We know that $n^k \leq k^n$, where $n^k$ is a polynomial and $k^n$ is an exponential function. However, what if we have a case such as $n^{10}$ and $1.001^n$. How can I determine which function will grow faster?

Background - this is a problem from my complexity class and specifically the topic about the Big O-Notation.

$\endgroup$
2
  • 1
    $\begingroup$ exponential beats polynomial; do you know L'hopital's rule? $\endgroup$ Feb 1, 2021 at 14:35
  • $\begingroup$ @J.W.Tanner Yes. Would I have to determine the limit of $n^{10}$ over $1.001^n$ and if the result is $0$, then $1.001^n$ grows faster? $\endgroup$
    – Ski Mask
    Feb 1, 2021 at 14:36

5 Answers 5

3
$\begingroup$

As other answers gave a way to actually prove the result, I would like to add something to "feel" why this is true, or at least a way to remember it without having to do the proof each time this question shows up in your life !

Surely, if one of the two functions grows faster than the other, the same can be said about their logarithms.

We will compare $\ln(1.001^n) = n \ln(1.001)$ and $\ln(n^{10}) = 10 \ln(n)$.

The graph of the first one is a straight line. It does not grow very fast, but still.

The graph of the second one is a "zoomed in" version of the graph of the $\ln$ function.

"Surely", the straight line will eventually cross the log curve.

(I know that this is very informal. However, this is an attempt at making things more "intuitive" rather than having to rely on computation and abstract rules. If it does not help, feel free to say so !)

$\endgroup$
2
$\begingroup$

We wish to determine if:

$$\lim_{n\to\infty}\frac{n^{10}}{1.001^{n}} < 1$$

Using l'Hopital's rule once:

$$\lim_{n\to\infty}\frac{n^{10}}{1.001^{n}} = \lim_{n\to\infty}\frac{10n^{9}}{\ln(1.001)1.001^{n}}$$

Twice:

$$=\lim_{n\to\infty}\frac{10n^{9}}{\ln(1.001)1.001^{n}} = \lim_{n\to\infty}\frac{10\cdot 9n^{8}}{\ln(1.001)^{2}1.001^{n}}$$

All the way until ten times:

$$ = \lim_{n\to\infty}\frac{10\cdot 9\cdot 8\cdots 2\cdot 1}{\ln(1.001)^{10}1.001^{n}} = \lim_{n\to\infty}\frac{\text{constant}}{1.001^{n}} = 0$$

Because the exponential grows without bound. Thus, $\boxed{1.001^{n}\text{ grows faster than }n^{10}.}$ Of course, this can be generalized to say that any function showing exponential growth will eventually be larger than any polynomial.

$\endgroup$
1
$\begingroup$

Let $f(n)=1.001^n$ and $g(n)=n^{10}$

For $n \approx 116735$ we have $f(n)=g(n)\approx 4.699\times 10^{50}$

and for $n>116735$ we have $f'(n)=\log_{e}(1.001)f(n) \approx 0.001 f(n)$ while $g'(n) = \frac{10}{n} g(n) \lt 0.0001 g(n) $

so for $n>116735$ we have $f(n) > g(n)$ and $f'(n) > g'(n)$

so past this point $1.001^n$ is larger than $n^{10}$ and is growing faster

$\endgroup$
0
$\begingroup$

We can say that $$(1.001)^n = e^{n\log(1.001)} \geq \frac{(n\log(1.001))^{11}}{11!} $$ using the series expansion of $e$. The result should then be clear.

$\endgroup$
0
$\begingroup$

An elementary argument.

Comparing $1.001^n$ and $n^{10}$ is the same as comparing $(\sqrt[10]{1.001})^n$ and $n$. To ease the computation, we note that $\sqrt[10]{1.001}>1.00001$, and we compare $1.00001^n$ to $n$.

Both $1.00001^n$ and $n$ grow unboundedly. (As you can check, $1.00001^{n+1}>1.00001^n+0.00001$, and this is enough to ensure growth.) Now after a while, $1.00001^n>100000$. Then $1.00001^{n+1}>100000+1$, and the exponential grows in steps larger than $1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .