# Which function increase faster?

I have these functions

$$f_{1}= \frac{n^{100}}{2^{n}}$$ $$f_{2}=2^{2^{n}}$$ $$f_{3}=n$$ $$f_{4}=10^{n}$$

how to put them in order from smaller to bigger?

My first thought is to divide for example $f_{4}$ with $f_{3}$ and then find the limit.

-
Do you know L'Hopital's rule? That can take care of at least a few of these. – Joe Johnson 126 Nov 6 '11 at 12:36
@Graphth Yes this is something you can understand only by looking at the functions. I mean how to prove it using math. – akimo_uki Nov 6 '11 at 12:36

$f_1$ does increase at first, very quickly, but eventually it decreases. In fact, it goes to 0. You can prove this with 100 applications of l'hopital's rule. Or, by induction, you can prove $n^k / 2^n$ goes to 0. Using that same idea, you can easily see that $f_3$ is the slowest growing of the 3 that do increase forever. That is, if you look at $\frac{n}{10^n}$, you see it goes to 0. If it goes to 0, then $10^n$ is increasing much faster than $n$. So, yes, this is your idea, as you stated above. Take quotients and find the limit. $f_4$ is in the middle, and $f_2$ is fastest.

-
f_1 increases from n=1 to n=2. If n=1, f_1=1/2. If n=2, f_1=2^(98). – Doug Spoonwood Nov 6 '11 at 13:02
That's why my original answer says "doesn't increase... forever." It does increase, but not forever. In the end, it goes to 0. But, I can see that my answer may be unclear, so let me change it to be more clear. Thanks. – Graphth Nov 6 '11 at 13:28

Yes, that would be the correct approach (that is, compute limits of $f_1/f_2$, etc..).

If we use the notation $f(n)\,\gg\,g(n)$ to mean $\lim\limits_{n\rightarrow\infty}\left|{{f(n)\over g(n)}}\right|=\infty$,

then $2^n \gg n^{100}$ (so $f_1\rightarrow 0$), $2^{2^n}\gg 10^n$, and $10^n\gg n$.

-

$\lim\limits_{n\to\infty}f_1(n)=0$, so after a certain point $f_1$ is a decreasing function. Clearly the linear function $f_3$ grows much more slowly than $f_2$ and $f_4$, both of which are at least exponential. Finally, $f_2$ grows much faster than $f_4$, because the exponent itself is exponential. Should you have any doubt of this, look at the logarithm of their ratio:

\begin{align*} \ln\left(\frac{2^{2^n}}{10^n}\right)=2^n\ln 2-n\ln 10\to\infty\text{ as }n\to\infty\;. \end{align*}

-