# Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply put them into a graphing application I saw online and the graph itself obviously showed the growth.

\begin{align} & 2^{\sqrt{\log n}}\\ & 2^n\\ & n^{4/3}\\ & n \log^3 n\\ & n^{ \log n}\\ & 2^{2^n}\\ & 2^{n^2} \end{align}

For example, I know that $2^{2^n}$ has the largest growth rate, with $2^{n^2}$ coming in second. I know this because if I plug the value of $5$ it turns into $2^{32}$ vs $2^{25}$, $6$ is $2^{64}$ vs $2^{36}$. But, is that the proof itself?

As far as the odd ones out, I have no idea how I could show a proof comparison of $n^{4/3}$ vs $n\log^3$n vs $2^n$, etc.

-
In general, this is a difficult problem. However, for your specific case, it is relatively tractable. "$f(n) << g(n)$" is equivalent to "$lg f(n) << lg g(n)$" for your examples. And a constant grows slower that $lg n$, which grows slower than $n^k$, which grows slower than $2^n$. – Craig Sep 19 '11 at 15:09
So, it's basically about identifying which ones are constants vs which ones are lg(n) vs which ones are n^k vs 2^n? – michael Sep 19 '11 at 15:15
Also, are you sure that a constant grows slower than lg(n)? It seems that lg(n) grows far slower... – michael Sep 19 '11 at 15:21
A constant function $f(n)=c$ doesn't grow at all, so I'm not sure why you think that it grows slower than a logarithmic function $g(n)=\log n$. – Chris Taylor Sep 19 '11 at 15:26
@Chris: Oh, i was trying to compare n^(4/3) vs n^(lg(n)) ... they both are n^k which i figure then I compare 4/3 to lg(n). Or, is that totally off? – michael Sep 19 '11 at 15:29

## 1 Answer

General Rules of Thumb which hold for sufficiently large $n$:

\begin{align} &\log^c(n) \leq n^{\epsilon}, \quad \text{ for any } \epsilon > 0, \quad \text { and any constant } c \\ \\ &n^k \leq k^n, \qquad \text{where } k \text{ is any constant } k > 1 \end{align}

As Chris noted above, we can write this as

$$A \ll \log^c (n) \ll n^{\epsilon} \ll k^n$$

To actually prove these rules, you just compute limits (assuming you know calculus). To see that $\log (n) \ll n^{\varepsilon}$ for example, just note that

$$\lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{n^{-1}}{\epsilon n^{\epsilon - 1}} = 0 = \lim_{n \to \infty} \frac{1}{\epsilon n^{\epsilon}} = 0.$$

where $A$ and $c$ are constants, $\epsilon > 0$, and $k$ is a real number such that $k > 1$.

If you want to show that $\log^c(n) \ll n^{\epsilon}$ for any positive integer $c$, then just note that

$$\lim_{n \to \infty} \frac{\log^c (n)}{n^\epsilon} \leq \left( \lim_{n \to \infty} \frac{\log (n)}{n^{\epsilon/c}} \right) \dots \left( \lim_{n \to \infty} \frac{\log(n)}{n^{\epsilon/ c}}\right) = 0$$ by what we showed above. We can actually take $c$ be to be any arbitrary real number and the above still holds. This is easy to see since every real number is less than or equal to some integer (infinitely many in fact!). I will leave it to you to show that $n \log^3 (n) \ll n^{4/3}$, for example. The more complicated functions work the same way but we might need to be slightly creative when evaluating the limits.

Hope this helps.

-