Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Assume I have a list of functions, for example

$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$

How do I sort them asymptotically, i.e. after the relation defined by

$\qquad f \leq_O g \iff f \in O(g)$,

assuming they are indeed pairwise comparable (see also here)? Using the definition of $O$ seems awkward, and it is often hard to prove the existence of suitable constants $c$ and $n_0$.

share|improve this question
2  
Since the OP never came back, I'm removing the localised stuff and make a reference question out of this. –  Raphael Feb 17 '13 at 9:40
add comment

5 Answers 5

up vote 16 down vote accepted

If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions.

If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then

  • $c=0 \qquad \quad\ \,\implies f \in o(g)$
  • $c \in (0,\infty) \quad \implies f \in \Theta(g)$
  • $c=\infty \qquad \ \ \ \implies f \in \omega(g)$

With this, you should be able to order most of the functions coming up in algorithm analysis¹. As an exercise, prove it!

Of course you have to be able to calculate the limits accordingly. Some useful tricks to break complicated functions down to basic ones are:

  • Express both functions as $e^{\dots}$ and compare the exponents; if their ratio tends to $0$ or $\infty$, so does the original quotient.
  • More generally: if you have a convex, continuously differentiable and strictly increasing function $h$ so that you can re-write your quotient as

    $\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$,

    with $g^* \in \Omega(1)$ and

    $\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$,

    then

    $\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

    See here for a rigorous proof of this rule (in German).

  • Consider continuations of your functions over the reals. You can now use L'Hôpital's rule; be mindful of its conditions²!

  • Have a look at the discrete equivalent, Stolz–Cesàro.
  • When factorials pop up, use Stirling's formula:

    $\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

It is also useful to keep a pool of basic relations you prove once and use often, e.g. $(\log n)^\alpha \in o(n^\beta)$ for all $\alpha, \beta > 0$ or $n^\alpha \in o(c^n)$ for all $\alpha$ and $c > 1$.


It can happen that above lemma is not applicable because the limit does not exist (e.g. when functions oscillate). In this case, consider the following characterisation of Landau classes using limes superior/inferior:

With $c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$ we have

  • $0 \leq c_s < \infty \iff f \in O(g)$ and
  • $c_s = 0 \iff f \in o(g)$.

With $c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$ we have

  • $0 < c_i \leq \infty \iff f \in \Omega(g)$ and
  • $c_i = \infty \iff f \in \omega(g)$.

Furthermore,

  • $0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$ and
  • $ c_i = c_s = 1 \iff f \sim g$.

Check here and here if you are confused by my notation.


¹ Nota bene: My colleague wrote a Mathematica function that does this successfully for many functions, so the lemma really reduces the task to mechanical computation.

² See also here.

share|improve this answer
add comment

Another tip: sometimes applying a monotone function (like log or exp) to the functions makes things clearer.

share|improve this answer
4  
This should be done carefully: $2n\in O(n)$, but $2^{2n}\notin O(2^n)$. –  Shaull Feb 17 '13 at 11:35
    
Seconded. The "apply monotone function" thing seems to be some kind of folklore which does not work in general. We have been working on sufficient criteria and have been come up with what I posted in the latest revision of my answer. –  Raphael Nov 8 '13 at 17:15
add comment

Tip: draw graphs of these functions using something like Wolfram Alpha to get a feeling for how they grow. Note that this is not very precise, but if you try it for sufficiently large numbers, you should see the comparative patterns of growth. This of course is no substitute for a proof.

E.g., try: plot log(log(n)) from 1 to 10000 to see an individual graph or plot log(log(n)) and plot log(n) from 1 to 10000 to see a comparison.

share|improve this answer
5  
Should we really recommend vodoo? –  Raphael Mar 27 '12 at 17:13
    
+1 for suggesting to draw graphs of the functions, although the linked graphs are rather confusing unless you know what they mean. –  Tsuyoshi Ito Mar 27 '12 at 17:35
    
I've improved the links. –  Dave Clarke Mar 27 '12 at 17:46
    
Note that adding "for n from 0 to 10000" (or similar) gives the plots a little more significance. You can at least use plots to save yourself effort, having only to compare $n-1$ pairs of functions rigorously. –  Raphael Mar 27 '12 at 17:48
    
Good suggestion, @Raphael. Question changed appropriately. –  Dave Clarke Mar 27 '12 at 18:50
add comment

I suggest proceeding according to the definitions of various notations. Start with some arbitrary pair of expressions, and determine the order of those, as outlined below. Then, for each additional element, find its position in the sorted list using binary search and comparing as below. So, for example, let's sort $n^{\log\log n}$ and $2^n$, the first two functions of n, to get the list started.

We use the property that $n = 2^{\log n}$ to rewrite the first expression as $n^{\log\log n} = (2^{\log n})^{\log\log n} = 2^{\log n\log\log n}$. We could then proceed to use the definition to show that $n^{\log\log n} = 2^{\log n\log\log n} \in o(2^n)$, since for any constant $c > 0$, there is an $n_0$ such that for $n \geq n_0$, $c(n^{\log\log n}) = c(2^{\log n\log\log n}) < 2^n$.

Next, we try $3^n$. We compare it to $2^n$, the largest element we have placed so far. Since $3^n = (2^{\log 3})^n = 2^{n\log3}$, we similarly show that $2^n \in o(3^n) = o(2^{n \log 3})$.

Etc.

share|improve this answer
add comment

Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual:

$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$ \gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$

share|improve this answer
    
That's an oddly specific list. Many of the relations (whatever $\gg$ means exactly) can be summarised to a handful of more general lemmata. –  Raphael Nov 8 '13 at 17:16
    
It's his notation for a dominance relation. –  Robert S. Barnes Nov 10 '13 at 10:14
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.