Determine if $1.001^n$ will grow faster than $n^{10}$.

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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