The Stack Overflow podcast is back! Listen to an interview with our new CEO.
4 of 6 deleted 203 characters in body

DPLL time complexity analysis

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