I was curious about the time complexity of Python's itertools.combinations function. I did some searching and it seems that many resources claim the time complexity is O(n!) or O(nCr).

However, for the two extremes of when r = 1 and r = n, the formula nCr reduces to n and 1, respectively. Does this mean we can conclude that the time complexity of itertools.combinations is O(n)?

CodePudding user response：

r=1 and r=n rather are (almost) best cases (actually r=0 is the lower extreme), not worst cases. Worst case, at least for number of combinations, is r=n/2. So if you do want to express the complexity in terms of just n, it's O(nC(n/2)) or O(n × nC(n/2)), depending on what you do with the tuples.

CodePudding user response：

Does this mean we can conclude that the time complexity of itertools.combinations is O(n)?

No you / we can't do that.

Consider this statement:

Algorithm X to compute the combinations of r values from a set of n is O(nCr).

It is in fact trivial to prove¹ that any algorithm to do the above must be at least O(nCr). But we would need to examine the actual code to determine that a given algorithm is exactly O(nCr)

What you are doing is setting one or both of the variables to fixed values. This is effectively changing the problem.

To illustrate this, we can just substitute the fixed values into the above statement; e.g.

Algorithm X to compute the combinations of 1 value from a set of n is O(nC1).

Since nC1 is n, we can rewrite this as:

Algorithm X to compute the combinations of 1 value from a set of n is O(n).

But notice that this problem is different to the original one.

In short ... this is NOT invalidating the original statement.

Note that the (alleged) claim that itertools.combinations is O(n!) is (I think) a misreading on your part. What that "source" actually says is:

"Getting all combinations of a list is O(n!). Since you're doing that n times to get combinations with different values of r, the whole algorithm is O(n * n!)."

My reading is that it is talking about Pn not nCr. But either way, it is too vague to be considered a credible source.

^{1 - Informal proof. The set of combinations of r from a set of n has nCr elements. Constructing this set will entail adding nCr elements to a data structure. That involves (at least) nCr memory writes. It will take (at least) O(nCr) time to do this ... assuming a (real world) computer with an upper limit on memory bandwidth.}