Complexity when generating all combinations

Question

Interview questions where I start with "this might be solved by generating all possible combinations for the array elements" are usually meant to let me find something better.

Anyway I would like to add "I would definitely prefer another solution since this is O(X)".. the question is: what is the O(X) complexity of generating all combinations for a given set?

I know that there are n! / (n-k)!k! combinations (binomial coefficients), but how to get the big-O notation from that?

Answer 1

First, there is nothing wrong with using O(n! / (n-k)!k!) - or any other function f(n) as O(f(n)), but I believe you are looking for a simpler solution that still holds the same set.

If you are willing to look at the size of the subset k as constant, then for k <= n - k:

n! / ((n - k)! k!) = ((n - k + 1) (n - k + 2) (n - k + 3) ... n ) / k!  

But the above is actually (n ^ k + O(n ^ (k - 1))) / k!, which is in O(n ^ k)

Similarly, if n - k < k, you get O(n ^ (n - k))

Which gives us O(n ^ min{k, n - k})

Answer 2

I know this is an old question, but it comes up as a top hit on google, and IMHO has an incorrectly marked accepted answer.

C(n,k) = n Choose k = n! / ( (n-k)! * k!)

The above function represents the number of sets of k-element that can be made from a set of n-element. Purely from a logical reasoning perspective, C(n, k) has to be smaller than

∑ C(n,k) ∀ k ∊ (1..n).

as this expression represents the power-set. In English, the above expression represents: add C(n,k) for all k from 1 to n. We know this to have 2 ^ n elements.

So, C(n, k) has an upper bound of 2 ^ n which is definitely smaller than n ^ k for any n, k > 3, and k < n.

So to answer your question C(n, k) has an upper bound of 2 ^ n for sure, but don't know if there is a tighter upper bound that describes it better.