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

-

1
– Ran G. Jan 30 at 7:35
– Rishi Prakash Jan 30 at 10:45

3
$O(d)^d$ is a weird one... – Raphael♦ Jan 30 at 12:41
@Raphael $O(\epsilon^{1/2^n})=O(1)$, so it is weird (but correct) as well. – Khaur Jan 30 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 at 17:16

## 1 Answer

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$. – Khaur Jan 30 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 Hudec Jan 30 at 19:40

1
Most people do, but you are trying to explain how the formalities work here, so you should probably also use $\in$. – Raphael♦ Jan 30 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 Hudec Jan 31 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 at 9:39
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 10, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9378015398979187, "perplexity_flag": "middle"}