Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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
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. –  Graphth Nov 6 '11 at 13:28
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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