I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these notations properly. Is there any way (Lecture notes or video lectures with examples) to understand these things clearly. Thank You.

  • 1
    $\begingroup$ If the basic definitions are clear to you, then terms like $2^{O(n)}$ should make sense as well. Make sure you really understand the basics, first. See cs.stackexchange.com/q/57/157 $\endgroup$
    – Ran G.
    Jan 30, 2013 at 7:35
  • $\begingroup$ videolectures.net/mit6046jf05_demaine_lec02 -- this was the video lecture I got help from. $\endgroup$ Jan 30, 2013 at 10:45
  • 3
    $\begingroup$ $O(d)^d$ is a weird one... $\endgroup$
    – Raphael
    Jan 30, 2013 at 12:41
  • $\begingroup$ @Raphael $O(\epsilon^{1/2^n})=O(1)$, so it is weird (but correct) as well. $\endgroup$
    – Khaur
    Jan 30, 2013 at 15:14
  • $\begingroup$ @Khaur In that case, it is (without context) not even clear whether $\varepsilon \to \infty$ or $d \to \infty$, or maybe even $\varepsilon \to 0$? $\endgroup$
    – Raphael
    Jan 30, 2013 at 17:16

1 Answer 1


That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.

I'll start with the full syntax of the big-O notation:

$$ f(n) = O(g(n)) $$

means that

$$ \exists C~\exists n_0~\forall n > n_0: f(n) \leq Cg(n). $$

So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.

Alternatively we can say $O(g(n))$ is a set of functions defined as

$$ O(g(n)) = \{ f(n) | \exists C~\exists n_0~\forall n>n_0: f(n) \leq Cg(n) \}. $$

And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.

Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. So instead we replace the big-O with a function that conforms to the big-O. Like this:

$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$

And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just

$$ c(n) = f(n)^n,\ f(n) = O(n) $$

In the set notation it makes even more sense, because

$$ g(F) = \{ g \circ f | f \ in F \} $$

where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:

$$ 2^{O(n)} = \{ 2^{f(n)} | f(n) \in O(n) \} $$


$$ O(n)^n = \{ f(n)^n | f(n) \in O(n) \}. $$

As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:

$$ f(n) = O(\epsilon^{1/2^n}) $$ $$ \exists C~\exists n_o~\forall n>n_0: f(n) < C\epsilon^{1/2^n} $$

(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm.

  • $\begingroup$ If you want to be formal on notation, remember that $O(g(n))$ is a class of functions, therefore $f(n)\in O(g(n))$, not $=$. Also $\epsilon^{1/2^n}$ tends to $1$ as $n$ tends to $\infty$. $\endgroup$
    – Khaur
    Jan 30, 2013 at 15:04
  • $\begingroup$ @Khaur: Well, that's the thing; most people write $f(n) = O(g(n))$ though using $\in$ is indeed more appropriate. Fixing the value. $\endgroup$
    – Jan Hudec
    Jan 30, 2013 at 19:40
  • 1
    $\begingroup$ Most people do, but you are trying to explain how the formalities work here, so you should probably also use $\in$. $\endgroup$
    – Raphael
    Jan 30, 2013 at 20:41
  • $\begingroup$ @Raphael: I'll add it; but usually the texts that use $=$, and it seems to be the more common form, define the expression as special notation and don't talk about class of functions at all. $\endgroup$
    – Jan Hudec
    Jan 31, 2013 at 6:47
  • $\begingroup$ @JanHudec Yes, but that routinely causes problems for beginners, because they have been conditioned to view $=$ as an equivalence relation (among other things). Just browse all the questions about asymptotics... $\endgroup$
    – Raphael
    Jan 31, 2013 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.