# Does input space size contribute at all to the runtime of an algorithm?

I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:

Given a set $$U$$ of $$n$$ elements, a collection $$S_1, \ldots, S_m$$ of subsets of $$U$$, and a number $$k$$, does there exist a collection of at least $$k$$ of these sets with the property that not two of them intersect?

This is I'm sure a very basic question, but I was wondering whether the amount of space in $$n$$ the input takes up matters at all in the formulation of runtime. This is the first example of an algorithm I've seen where the input itself takes up space exponential in $$n$$ since of course there are $$2^n$$ possible subsets of $$U$$. Thus, it seems that possibly the time needed to allocate the space necessary to even "handle" the input prevents there from being a polynomial time algorithm.

Or rather, do we just assume that the input magically appears in our hands already allocated before we start keeping track of algorithm runtime? And as a side question, can we choose what data structure it is given to us in? This seems more natural to me, but I wanted to make sure. I know, for example, that the time needed to allocate an output (or allocate anything in between) does matter.

• Your program doesn't have to read all possible 2^n subsets of U; just the ones provided as input. The input for this problem is a set of size n, m sets of size at most n, and one scalar number, which can all be read in time polynomial in m and n; more generally, when talking about a "polynomial time" algorithm, that means polynomial in the input size, and it is surely impossible for the input size to be exponential in itself. Feb 11 '20 at 0:03
• @kaya3 Thanks for the response! I still have a question though: With this formulation, wouldn't Set Cover be solvable in polynomial time? All I have to do is iterate over the ${m \choose k}$ subsets of size $k$ of $\{ S_1, \ldots , S_m \}$ and for each collection of subsets check whether no two of them intersect. Checking for intersections in each iteration would I believe take $O(n^2 m^2)$, though that might be off. Regardless it seems to be polynomial. The key fact being we don't need to check collections of size greater than $k$ since if there is a collection of size... Feb 13 '20 at 21:05
• @kaya3 ...greater than $k$ where no two $S_i$ intersect then there is a collection of size exactly $k$ where no two intersect. Feb 13 '20 at 21:07
• In general (m choose k) is polynomial in m but exponential in k, and the number of bits needed to describe the input (i.e. m sets of size <= n, plus the scalar k) is not exponential in k. Feb 13 '20 at 21:13
• @kaya3 Ah I'm so used to the second part of the choose operation being a constant that I forgot it is actually exponential. Thanks! Feb 13 '20 at 21:18

We measure the running time as a function of the length of the input, not as a function of $$n$$. So, it doesn't matter whether the length of the input is $$2^n$$ or not.
When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $$n$$).
For your problem, the length of the input could be $$2^n$$, but it will typically be a lot less than $$2^n$$, because typically we'll have many fewer sets than that. Either way, it doesn't matter, because we're measuring the running time as a function of the input length.