# For a given k-DNF formula, what is the size of the formula for the purpose of complexity?

I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $$n$$ in the time complexity would refer to in this case (that is that I don't know how the "size" of a k-DNF is defined, nor was it defined in the assignment). Is it the number of clauses, the number of literals (distinct or nondistinct?) or something else? I think they should all be equivalent for the purpose of complexity, but I would rather adopt the standard convention.

• Number of literals. – Yuval Filmus Feb 10 at 4:14

## 1 Answer

The two standard conventions are number of clauses and number of literals (counted with repetition!). The two measures are within a factor of $$n$$ of each other.