Complexity of enumeration vs complexity of counting 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.
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$.