0
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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})$.

$\endgroup$
5
  • 1
    $\begingroup$ Adding to your answer, $n \choose k$ $= \Theta(n^k)$, assuming $k$ is constant. See proof here. $\endgroup$ Aug 30, 2021 at 12:28
  • $\begingroup$ @DillonDavis Thank you very much! This is very helpful! $\endgroup$ Aug 31, 2021 at 3:25
  • $\begingroup$ @InuyashaYagami Thanks. One question, what does the notation $\Theta(\cdot)$ mean? $\endgroup$ Aug 31, 2021 at 3:27
  • 2
    $\begingroup$ @T34driver its big-theta notation; it denotes a tight upper AND lower bound on the time complexity, simultaneously. $\endgroup$ Aug 31, 2021 at 4:08
  • $\begingroup$ @DillonDavis I see. Thanks! How to interpret the fact that the tight upper and lower bound on the time complexity is $n^k$. $\endgroup$ Aug 31, 2021 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.