# Does $2^{O(n)}$ mean $O(2^n)$? If not, what does $2^{O(n)}$ mean?

In this "tutorial", in the end, they say exponential asymptotic notation is $$2^{O(n)}$$.

Is $$2^{O(n)}$$ the same thing as $$O(2^n)$$? Is there any reason to notate it that way?

According to one of the answers, they are different. But then according to the "tutorial", $$O(f(n))$$ is a set. So how is the expression $$2^{O(n)}$$ meaningful?

(Specifically they define $$O(f(n)) = \{ g(n) :$$ exists $$c \gt 0$$ and $$n_0 \gt 0$$ such that $$f(n) \leq c*g(n)$$ for all $$n \gt n_0$$).

• $f(n)=2^{O(n)}$ means $\log_2 f(n)=O(n).$ – Thomas Andrews Apr 24 at 14:56

## 2 Answers

A function $$f:\mathbb N\to\mathbb R$$ is $$2^{O(n)}$$ if and only if there is a constant $$C$$ such that for all $$n$$ large enough we have $$f(n)\le 2^{Cn}$$.

We can think of the $$O$$ notation as decribing a family of functions. So, $$2^{O(n)}$$ would be the family of functions satisfying the requirements just indicated.

In contrast, a function $$f$$ is $$O(2^n)$$ if and only if there is a constant $$K$$ such that for all $$n$$ large enough we have $$f(n)\le K 2^n$$.

It should be clear that $$O(2^n)\subset 2^{O(n)}$$, that is, any function that is $$O(2^n)$$ is also $$2^{O(n)}$$. The converse fails, however: consider $$f(n)=2^{2n}$$.

• Would it make sense to use "composite" of big-O notation for functions other than $2^n$ too? ie. $f: \mathbb{N} \rightarrow \mathbb{R}$ is $g( O(n) )$ for a real function $g$ iff there's a constant $C$ such that for all $n$ large enugh we have $f(n) \leq g( Cn )$ ? – RUBEN GONÇALO MOROUÇO Apr 24 at 14:20
• Sure, that would be the natural interpretation of the notation. Of course, if you are using it in a writing of your own, it may be best to first remind the reader of its meaning, to avoid confusion. – Andrés E. Caicedo Apr 24 at 14:21
• Shouldn't $2^{O(n)}$ include a positive lower bound on $f$ as well? – Umberto P. Apr 24 at 15:10
• @Umberto It is a matter of convention. Sure, some sources say that $f$ is $O(g)$ if and only if $|f(n)|\le C g(n)$ for some $C$ and all $n$ large enough. In that case, yes, we need some such lower bound as well (in the form: $f$ is $O(2^n)$ if and only if $|f(n)|\le 2^{Cn}$ for some $C$ and all large $n$). In many settings, though, all functions are assumed positive, and so the inclusion of the absolute value is redundant. It depends on the context. – Andrés E. Caicedo Apr 24 at 15:15

No, it isn't the same. $$2^{3n}$$ is $$2^{O(n)}$$ but not $$O(2^n)$$

• Hmm makes sense. What is the meaning of $2^{O(n)}$ then? According to their definition $O(f(n))$ is a set. How can $2$ to the power of a set be meaningful in this context? – RUBEN GONÇALO MOROUÇO Apr 24 at 14:08
• I see that Andrés E. Caicedo has already addressed this. – saulspatz Apr 24 at 14:16