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

share|improve this question
1  
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
2  
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
show 4 more comments

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.

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.