6 Add 'time-complexity' tag | link edit approved Apr 2 '18 at 10:19 Grant Miller 13322 gold badges22 silver badges1111 bronze badges 5 added 40 characters in body edited Aug 12 '15 at 16:59 matheuscscp 21233 silver badges1010 bronze badges Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(m)$$ cost is amortized. Hence, its running time should also be $$O(m 2^n)$$. Then why everybody saysStill, some places state that DPLL running time is $$O(2^n)$$? I really can't see how the hell is also an upper bound for DPLL $$m 2^n = \Theta(2^n)$$(Wikipedia, for example). Does anybody knows the analysis to find this upper bound? Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(m)$$ cost is amortized. Hence, its running time should also be $$O(m 2^n)$$. Then why everybody says that DPLL running time is $$O(2^n)$$? I really can't see how the hell $$m 2^n = \Theta(2^n)$$. Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(m)$$ cost is amortized. Hence, its running time should also be $$O(m 2^n)$$. Still, some places state that $$O(2^n)$$ is also an upper bound for DPLL (Wikipedia, for example). Does anybody knows the analysis to find this upper bound? 4 deleted 203 characters in body edited Aug 12 '15 at 16:31 matheuscscp 21233 silver badges1010 bronze badges Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. But we know that $$m$$ is a polynomial in $$n$$, so $$m = \Theta(n^k)$$ and the algorithm runs in $$O(n^k 2^n)$$, for some $$k \geq 1$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(n^k)$$$$O(m)$$ cost is amortized. Hence, its running time should also be $$O(n^k 2^n)$$$$O(m 2^n)$$. Then why everybody says that DPLL running time is $$O(2^n)$$? I really can't see how the hell $$n^k 2^n = \Theta(2^n)$$. Is easy to see that $$\lim_{n\to\infty} \frac{n^k 2^n}{2^n} = \infty$$$$m 2^n = \Theta(2^n)$$. Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. But we know that $$m$$ is a polynomial in $$n$$, so $$m = \Theta(n^k)$$ and the algorithm runs in $$O(n^k 2^n)$$, for some $$k \geq 1$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(n^k)$$ cost is amortized. Hence, its running time should also be $$O(n^k 2^n)$$. Then why everybody says that DPLL running time is $$O(2^n)$$? I really can't see how the hell $$n^k 2^n = \Theta(2^n)$$. Is easy to see that $$\lim_{n\to\infty} \frac{n^k 2^n}{2^n} = \infty$$. Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $$\phi$$ when all the $$n$$ variables have values assigned. Let $$m$$ be the size of $$\phi$$. Then the time complexity for this backtracking is $$O(m 2^n)$$. Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $$\phi$$ along the backtracking, instead of doing it only at once, so the $$O(m)$$ cost is amortized. Hence, its running time should also be $$O(m 2^n)$$. Then why everybody says that DPLL running time is $$O(2^n)$$? I really can't see how the hell $$m 2^n = \Theta(2^n)$$. 3 fixed a typo; k -> n edited Aug 10 '15 at 17:20 Kyle Jones 6,08711 gold badge1919 silver badges4141 bronze badges 2 edited tags | link edited Aug 10 '15 at 16:15 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 1 asked Aug 10 '15 at 15:16 matheuscscp 21233 silver badges1010 bronze badges