How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Question

Given the following functions i need to arrange them in increasing order of growth
a) $2^{2^n}$
b) $2^{n^2}$
c) $n^2 \log n$
d) $n$
e) $n^{2^n}$
My first attempt was to plot the graphs but it didn't gave the correct answer so I took a look on How do I determine the increasing order of growth of a set of functions? and calculated the log for all the functions listed above and got

a) $2^{2^n} \Rightarrow 2^n + \log 2$
b) $2^{n^2} \Rightarrow n^2 + \log 2$
c) $n^2 \log n \Rightarrow 2\log n + \log \log n$
d) $n \Rightarrow \log n$
e) $n^{2^n} \Rightarrow 2^n + \log n$

and then i plotted them on graph and got the answer : dcbea but when i submitted the answer it seems to be incorrect. What i am doing wrong?

Answer 1

To answer @sol4me If you know some better way then please share, i will be glad to know.

First, never trust a plot. You just saw it may hurt, so even if it can help, it's not a proof.

Then, you must know some basic comparison scales, for example, as $n\rightarrow \infty$, and fixed $a>0, b>0, c>1$ and any real $d$,

$$d \ll \log \log n \ll \log^a n \ll n^b \ll c^n \ll n! \ll n^n$$

Where I write $a_n \ll b_n$ iff $\frac{a_n}{b_n} \rightarrow 0$ (this is not a standard notation !)

Of course, there are many other possible asymptotic comparisons, these are just the most frequent.

You have also some allowed operations, for example,

• if $\xi>1$ is a fixed real and $1 \ll a_n \ll b_n$, then $\xi^{a_n} \ll \xi^{b_n}$.
• if $s_n \ll a_n$ and $s_n \ll b_n$, and if $a_n \ll b_n$, then $a_n + s_n \ll b_n + s_n$.

You prove such things by computing the limit. Taking $\log$ as you did may be very useful (for example in the first case above).

Finally, you have to apply these comparisons to your case, and sometimes it's a bit tricky, but honestly here it's not.

• $n^2 \ll 2^n$ so $2^{n^2} \ll 2^{2^n}$
• $2 \ll n$, so $2^{2^n} \ll n^{2^n}$. If in doubt, write the quotient $a_n=\left(\frac{2}{n}\right)^{2^n}$, and since $\frac{2}{n}<\frac{1}{2}$ as soon as $n>4$, you have $a_n \rightarrow 0$
• $1 \ll \log n $, so $n^2 \ll n^2 \log n$, and since $n \ll n^2$, you have $n \ll n^2\log n$.
• $n \ll n^2$ so $2^n \ll 2^{n^2}$, and also $\log n \ll n$ so $n^2 \log n \ll n^3$. Then $n^3 \ll 2^n$, hence $n^2\log n \ll n^3 \ll 2^n \ll 2^{n^2}$, and especially $n^2 \log n \ll 2^{n^2}$.

When you have a doubt, write what the comparison means as a limit, and compute the limit.

And remember, these comparisons are asymptotic. Sometimes the smallest $n$ such that the inequality really holds may be very large, but it's nevertheless only a fixed, finite number. You may have inequality for $n> 10^{10^{10}}$ for example, so trying to plot things is often hopeless.

If you want to know more about such methods, there are good readings, such as Concrete Mathematics, by Graham, Knuth and Patashnik.

Answer 2

As @Jean-Claude Arbaut mentioned, the problem was in calculating log. To summarize we need to first calculate the log for all the functions and then plot them for wide range of number. I plotted it here