Complexity when generating all combinations

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

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.