patternMinor
When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?
Viewed 0 times
meantexponentialtimesaidalgorithmhaswhenrunscomplexity
Problem
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.
Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.
Solution
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$.
Your titular question should answer itself now.
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.
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$.
Your titular question should answer itself now.
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.
Context
StackExchange Computer Science Q#85703, answer score: 4
Revisions (0)
No revisions yet.