Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
7  
Testing the satisfiability of a Boolean formula by enumerating all possible assignments? – joriki Apr 4 '11 at 16:02
5  
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
4  
any algorithm that enumerates the subsets of a set to find a subset with a certain property – joriki Apr 4 '11 at 16:22
2  
@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
2  
@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
show 15 more comments

3 Answers

up vote 4 down vote

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).

share|improve this answer
Just curious: Your last sentence means that if the exponential time hypothesis is true, then P=BPP? – chazisop Apr 4 '11 at 21:35
1  
up vote 1 down vote

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*}$$

share|improve this answer
1  
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
1  
@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
show 8 more comments
up vote 0 down vote

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?

share|improve this answer
3  
No. Try $2^{3n}$. – Did Apr 4 '11 at 16:26
@Didier Piau: right, thanks! – Matt N. Apr 4 '11 at 16:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.