# asymptotic notations with two exponents

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.

• 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 Jan 30 '13 at 7:35
• videolectures.net/mit6046jf05_demaine_lec02 -- this was the video lecture I got help from. Jan 30 '13 at 10:45
• $O(d)^d$ is a weird one...
– Raphael
Jan 30 '13 at 12:41
• @Raphael $O(\epsilon^{1/2^n})=O(1)$, so it is weird (but correct) as well. Jan 30 '13 at 15:14
• @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$?
– Raphael
Jan 30 '13 at 17:16

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.

$$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) \}$$

and

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

• 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$. Jan 30 '13 at 15:04
• @Khaur: Well, that's the thing; most people write $f(n) = O(g(n))$ though using $\in$ is indeed more appropriate. Fixing the value. Jan 30 '13 at 19:40
• Most people do, but you are trying to explain how the formalities work here, so you should probably also use $\in$.
– Raphael
Jan 30 '13 at 20:41
• @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. Jan 31 '13 at 6:47
• @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...
– Raphael
Jan 31 '13 at 9:39