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

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!

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})$$.
• Adding to your answer, $n \choose k$ $= \Theta(n^k)$, assuming $k$ is constant. See proof here. Aug 30, 2021 at 12:28
• @InuyashaYagami Thanks. One question, what does the notation $\Theta(\cdot)$ mean? Aug 31, 2021 at 3:27
• @DillonDavis I see. Thanks! How to interpret the fact that the tight upper and lower bound on the time complexity is $n^k$. Aug 31, 2021 at 4:25