# Common algorithm with an order of Θ(2^n)

What would be a common algorithm with an order of Θ(2^n)? When I say "order", I mean time complexity analysis. I was thinking exponential growth but are there any that are more computer science oriented?

-
Testing the satisfiability of a Boolean formula by enumerating all possible assignments? –  joriki Apr 4 '11 at 16:02
Do you mean to ask for algorithms which run in $\Theta(2^n)$? (Any polynomial algorithm is $O(2^n)$.) Are you looking for best-known algorithms that run in $\Theta(2^n)$, or does any problem with a natural $\Theta(2^n)$ algorithm suffice? Do you care about additional polynomial factors? For example, the natural dynamic programming solution to the Traveling Salesman Problem runs in $\Theta(2^n \cdot n^2)$. –  Zach Langley Apr 4 '11 at 16:17
any algorithm that enumerates the subsets of a set to find a subset with a certain property –  joriki Apr 4 '11 at 16:22
@Trevor: Your question is ambiguous. You say $O(2^n)$. Even printf("hello world") is $O(2^n)$. Once someone points out a mistake (see Zach's comment), why don't you edit the question to correct it? Also, you are missing the model of computation. I presume you mean the word RAM model. –  Aryabhata Apr 4 '11 at 17:05
@Trevor: I would say BigOh is most commonly misused in algorithm analysis. Take your question for instance. Were you looking for O(n) time algorithms? Probably not, but O(n) algorithms are also O(2^n)... –  Aryabhata Apr 4 '11 at 18:48

The naive algorithm for $3$-coloring takes time $2^n$, though this is not optimal (Wikipedia mentions a $1.3289^n$ algorithm). Lots of other NP-complete programs have $2^n$ algorithms (or in general $c^n$), and it is conjectured that some of them in fact require time $c^n$; if this is true then randomness doesn't help for efficient computation (BPP=P).

-
Just curious: Your last sentence means that if the exponential time hypothesis is true, then P=BPP? –  chazisop Apr 4 '11 at 21:35
–  Yuval Filmus Apr 4 '11 at 21:40

A typical algorithm with $\mathcal O(2^n)$ performance is the naive algorithm to calculate the Fibonacci-numbers. As they are defined as

$$\begin{eqnarray*}F_0&=&0\\F_1&=&1\\F_n&=&F_{n-1}+F_{n-2}\end{eqnarray*}$$

-
While what you stated is technically true ($\mathcal{O}(2^n)$), it is not $\theta(2^n)$, it is $\theta(\phi^n)$, where $\phi$ is the golden ratio. –  Aryabhata Apr 4 '11 at 17:03
Hm... I'm not a mathematician. Thank you. –  FUZxxl Apr 4 '11 at 17:08
I don't understand. $F_n$ grows as $\phi^n$, so we need of order $n$ digits to represent it, so we need time of order $n^2$ to carry out the $n$ additions required to get up to $F_n$ -- where does the exponential growth come from? –  joriki Apr 4 '11 at 17:16
@joriki: Assuming integer addition is $O(1)$, if we do a naive recursion, then we get $\phi^n$. –  Aryabhata Apr 4 '11 at 17:18
@Michael: The time complexity also satisfies $T(n) = T(n-1) + T(n-2)$. If it was $T(n) = 2T(n-1)$, I would agree with you. –  Aryabhata Apr 4 '11 at 17:35

According to Wikipedia, "Solving the traveling salesman problem using dynamic programming" is an exponential time problem. They write $2^{O(n)}$, I'm not sure it's the same as $O(2^n)$. Am I right in thinking that it is the same?

-
No. Try $2^{3n}$. –  Did Apr 4 '11 at 16:26
@Didier Piau: right, thanks! –  Rudy the Reindeer Apr 4 '11 at 16:50