3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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 ) $ ? $\endgroup$ – RUBEN GONÇALO MOROUÇO Apr 24 at 14:20
  • $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Apr 24 at 14:21
  • $\begingroup$ Shouldn't $2^{O(n)}$ include a positive lower bound on $f$ as well? $\endgroup$ – Umberto P. Apr 24 at 15:10
  • $\begingroup$ @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. $\endgroup$ – Andrés E. Caicedo Apr 24 at 15:15
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – RUBEN GONÇALO MOROUÇO Apr 24 at 14:08
  • $\begingroup$ I see that Andrés E. Caicedo has already addressed this. $\endgroup$ – saulspatz Apr 24 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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