Difficulty creating all combinations

Question

Interview questions in which I start with “this can be resolved by creating all possible combinations for array elements” usually mean that I can find something better.

In any case, I would like to add: "I would definitely prefer a different solution, as it is O (X)." Question: what is the complexity of O (X) for creating all combinations for a given set?

I know there is n! / (Nk)! k! combinations (binomial coefficients), but how do you get the Big-O designation from them?

Answer 1

Firstly, there is nothing wrong with using O(n! / (nk)!k!) - or any other f(n) function like O(f(n)) , but I believe you are looking for a simpler solution, which still contains the same set.

If you want to look at the size of the subset k as a constant,

for k <= nk:

 n! / ((nk)!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 nk<k , you get O(n^(nk))

What gives us O(n^min{k,nk})

Answer 2

As a continuation of @amit, the upper bound min {k, nk} is n / 2.

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

Answer 3

case1: if nk <k

Suppose that n = 11, k = 8 and nk = 3, then

  n!/(nk)!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 nk=3 so it become O(n^(nk)) 

case2: if k <nk

Suppose that n = 11, k = 3 and nk = 8, then

  n!/(nk)!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)) 

What gives us O (n ^ min {k, nk})

Answer 4

I know this is an old question, but it is popular on Google, and IMHO has an incorrectly marked accepted answer.

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

The above function represents the number of k-element sets that can be made from an n-element set. Purely from a logical point of view, C(n, k) should be less than

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

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

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

Therefore, to answer your question, C(n, k) probably has an upper bound of 2 ^ n , but I don’t know if there is a tougher upper bound that describes it better.