3 of 6 fixed a typo; k -> n

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