# Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?

• It could also be in terms of the input length. Do you have any specific analysis in mind? Usually they explain what their variables mean. Aug 28 '13 at 21:07
• http://en.wikipedia.org/wiki/DPLL_algorithm Worst case complexity says it's O(e^n).
– Rich
Aug 28 '13 at 21:09
• Here $n$ is probably input length. But don't trust Wikipedia - find an actual source. I see that Wikipedia doesn't quote any, so there's no reason to believe it. In particular, I suspect that by $O(e^n)$, they really mean $O(c^n)$ for some constant $c > 1$. Aug 28 '13 at 21:19
• Input length being the number of clauses? Or the number of vairables. The DPLL is used to solve k-SAT, which is known to be NP-complete. However, I don't understand if it is NP-complete based on the number of variables or the number of clauses.
– Rich
Aug 29 '13 at 23:14
• Input length being the length of the input as a string. Roughly the total number of literals appearing in all the clauses. Aug 30 '13 at 22:11