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?

Quesnay

Are you referring to k as constant? Is O(k!) is O(1) ? If so, complexity is O(n^min{k,n-k}). Otherwise - not sure you simplify it much. – Whipperin

yes, given k as a constant. – Quesnay

@Whipperin If k is a constant, the complexity will be O(n^k), since k < n-k for a sufficiently large n – Upthrust

If I wanted to mention it, I would say "Generating all the combinations takes exponential time, so ...". Note that as an interviewer, I don't want to be left with the impression that you would consider an exponential time solution to be acceptable under any circumstances. Maybe start with "Of course we don't want to take exponential time for this, so..." – Saddlery

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

Whipperin

The upper bound of n^k leaves quite some gap above n! / ( (n-k)! * k! ) . IMHO 2 ^ n is a smaller upper bound than n! / ( (n-k)! * k! ) . Look at my answer below – Asthenosphere

Can you explain how i can understand this line. ``But the above is actually (n^k + O(n^(k-1))) / k!, which is in O(n^k)`. How did you derived this conclusion. – Rhee

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.

Asthenosphere

"2 ^ n is definitely smaller than n ^ k..." This is not right. 2^n is larger than n^k for large n. In other words, Iim(2^n/n^k)=∞ when n->∞ – Madoc

Answer 3

As a follow-up to @amit, an upper bound of min{k, n - k} is n / 2.

Therefore, the upper-bound for "n choose k" complexity is O(n ^ (n / 2))

Crisscross

In the task of generating all k-combinations of an n-set, k is fixed. Therefore O(n^k) is a better (tighter) estimation. – Madoc

Answer 4

case1: if n-k < k

Let suppose n=11 and k=8 and n-k=3 then

 n!/(n-k)!k! = 11!/(3!8!)= 11x10x9/3!
 let suppose it is (11x11x11)/6 = O(11^3) and 11 was equal to n so O(n^3) and also n-k=3 so it become O(n^(n-k))

case2: if k < n-k

Let suppose n=11 and k=3 and n-k=8 then

 n!/(n-k)!k! = 11!/(8!3!)= 11x10x9/3!
 let suppose it is (11x11x11)/6 = O(11^3) and 11 was equal to n so O(n^3) and also k=3 so it become O(n^(k))

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

Penknife