What's the time complexity of finding all size-$k$ combinations from a set of size $n$?

Question

I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time complexity of finding all combinations of all sizes (involving ${n\choose 1}+{n\choose 2}+...{n\choose n} $ operations)? I need to add a remark on this in a project of mine, but I have zero training or background in computer science.

My guess is that the time complexity of the former is $O({n\choose k})$ and that the time complexity of the latter is $O({n\choose 1}+{n\choose 2}+...{n\choose n})$. Is this correct?

It would be great if you could add some intuition in your explanation. Thanks!

Answer 1

Your first guess is correct- the time complexity of finding all size-k combinations is $O({n\choose k})$. This can be done by first ordering your set, and then selecting each element from this set in turn, and combining it with each size-k-1 combination of elements ordered to be after the element itself, recursively.

Regarding the second question- the worst-case time complexity to find all combinations of all sizes is indeed greater, and your guess is almost correct. Technically, we need to count the empty set / combination of 0 elements, which there is exactly one of, so $O({n\choose 0}+{n\choose 1}+...{n\choose n})$, which simplifies to merely $O({2^n})$.