# When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

Also, are they equivalent or are they different?

Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.

Beware the abuse of notation; I can not recommend using "$2^{O(n)}$".

That said, a common interpretation is using the placeholder semantic. That is, we read

$\qquad\displaystyle f \in 2^{O(n)} \quad"\iff"\quad \exists\, g \in O(n).\ f \in O(2^{g(n)})$

Compare that to the definition of $O(2^n)$ and you'll quickly see that the two are not the same.

Because $2^{cn} = (2^c)^n$, the term "$2^{O(n)}$" covers all exponentially bounded functions, i.e. the union of all $O(a^n)$; use $c = \log_2 a$.

Since $3^n \not\in O(2^n)$, this Landau class does not cover all exponential function. This is easy to show independently of above discussion, by the way.
Note how the "definition" makes two $O$ out of one; that's why I think that notation is bad. See also this related question where is becomes clear that even experts don't agree on what the notation should mean here, exactly. Here's another related question.
• The notation $2^{O(n)}$ is used a lot when the main result is whether or not there exist single exponential algorithms. We've had this discussion before, and I'm not going to be able to convince you, but in my opinion, shared by many researchers in algorithms, the notation $2^{O(n)}$ is quite handy. Dec 20, 2017 at 14:05