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?
Common algorithm with an order of Θ(2^n)
1
$\begingroup$
algorithms
computer-science
examples-counterexamples
-
0Not much of an example, but a naïve implementation of the simplex method for linear programming will require exponential time if given the Klee-Minty problem. – 2011-04-07
2 Answers
4
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).
-
1See http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf. – 2011-04-04
0
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?
-
0@Didier Piau: right, thanks! – 2011-04-04