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)?
>Solution :
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.