4
$\begingroup$

In the context of complexity, I have seen both $O(2^{n})$ and $2^{O(n)}$ used.

Whats the difference between the two?

$\endgroup$

2 Answers 2

14
$\begingroup$

$2^{O(n)}$ is larger. For $O(2^n)$ is exactly functions bounded by $K\cdot 2^n$ for some large $K$, while $2^{O(n)}$ includes things like $4^n = 2^{2n}$, which is not $O(2^n)$.

$\endgroup$
1
$\begingroup$

$f(n)=O(2^n)$ means there exists constant $M>0$ such that $\mid f(n) \mid \leq M.2^n$ whereas $f(n)=2^{O(n)}$ means there exists constant $M>0$ such that $\mid f(n)\mid \leq 2^{M.n}$ for large $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .