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.
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.

Typically, the format/representation of the input doesn't affect the running time much; the running time will be identical for any reasonable way to represent or encode the input.  So, typically that doesn't matter.  In the cases where it does matter, be careful to specify the input representation, or ask if it isn't specified.