1
$\begingroup$

I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm.

Now, I have problem with the following. Let say that we have to count the number of positive integers less or equal than positive integer $N$. We know that the answer is $N$ and therefore we can solve the counting problem in $\mathcal{O}(1)$. Corresponding enumeration problem is to output every positive number and this can be done in $\mathcal{O}(N)$ steps and I believe that this is pseudo-polynomial complexity and that in fact complexity is exponential.

Are these complexity assumptions correct? Is the number of solutions of counting problem always bounded by the time complexity of corresponding enumeration algorithm?

Any hints or suggestions appreciated.

$\endgroup$
2
$\begingroup$

Yes. An enumeration algorithm executes at least 1 step (an instruction, line of code, or whatever else your metric is) for every instance it finds, so there's at least as many steps as there are instances to count.

Just remember that if you use an asymptotic time complexity like $O(N)$, it doesn't tell you enough for an exact bound on the count. For example, it takes $O(N)$ time to enumerate $1,\dots,2N$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.