4
$\begingroup$

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.

  • 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$.2011-09-19
  • 0
    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?2011-09-19
  • 0
    Also, are you sure that a constant grows slower than lg(n)? It seems that lg(n) grows far slower...2011-09-19
  • 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$.2011-09-19
  • 0
    @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?2011-09-19
  • 0
    @Chris: Oh, and 2^sqrt(lg(n)) seems to be the slowest growing one, yet it's a 2^n item (an adjusted n)?2011-09-19
  • 0
    Ok, it was just a misunderstanding then. When Craig and I said `a constant grows slower than $\log n$' we meant that a constant function grows slower than a logarithmic function. What Craig pointed out is that saying $f(n)\ll g(n)$ is equivalent to saying $\log f(n)\ll \log g(n)$ (since $\log$) is a monotonic increasing function) and so you can compare the growth rates of $n^c$ and $n^\log n$ by comparing the growth rates of $c$ and $\log n$, as you seem to be doing.2011-09-19
  • 0
    Notice that $n^{4/3} = (e^{4/3})^{\log n}$ which allows you to compare the growth rate with $2^{\sqrt{\log n}}$ by taking logs.2011-09-19
  • 0
    @ChrisTaylor, I'm not *as* lost, but still a bit. I guess I know the order, but the whole part of showing a proof to it outside of just plugging in values gets me. And, the mixed bag of types makes it harder as well. If it were just 2^n vs 2^n^2 vs 2^lg(n) that would be easy...2011-09-19

1 Answers 1