# What is $2^{O(n)}$? [duplicate]

How can I interpret a time complexity of $$2^{O(n)}$$? Is it simply equal to $$O(2^n)$$?

I'm pretty new to this, so would appreciate any kind of help.

$$O(2^{O(n)})$$ means: It is $$O(2^{f(n)})$$ for some function f with f(n) ≤ cn for large n.
So this could be $$O(2^n)$$ if c = 1, or $$O(2^{2n})$$ = $$O(4^{n})$$ if c = 2, or $$O(2^{100n})$$ = $$O((2^{100})^{n})$$ if c = 100. We don't know. All we know is it grows pretty fast, and we can't simply express it as O(something).
The expression "$$2^{O(n)}$$" is shorthand for "$$2^{f(n)}$$ for some function $$f(n) = O(n)$$". For example, $$3^n = 2^{O(n)}$$. This example also demonstrates that a function which is $$2^{O(n)}$$ is not necessarily $$O(2^n)$$, though the opposite does hold.