1
$\begingroup$

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.

  • 0
    @Graphth Y$e$s this is something you can understand only by looking at the functions. I mean how to prove it using math.2011-11-06

3 Answers 3

3

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

  • 1
    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.2011-11-06
1

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

0

$\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*}$