CODEWITHSUNDEEP
algorithmlanguage-agnosticbig-otime-complexitycombinations
Albert
Albert

Reputation: 1123

Complexity when generating all combinations

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?

Upvotes: 28

Views: 22801

Answers (4)

Abdu
Abdu

Reputation: 497

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

Upvotes: 6

amit
amit

Reputation: 178481

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

Upvotes: 32

Vikhram
Vikhram

Reputation: 4404

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.

Upvotes: 14

Muhammad Kashif Arif
Muhammad Kashif Arif

Reputation: 668

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

Upvotes: 0

Related Questions