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

Question

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

Answer 1

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

Answer 2

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