What Is The Computational Complexity Of `itertools.combinations` In Python?

itertools.combinations in python is a powerful tool for finding all combination of r terms, however, I want to know about its computational complexity. Let's say I want to know th

Solution 1:

I had this same question too (For itertools.permutations) and had a hard time tracing the complexities. This led me to visualize the code using matplotlib.pyplot;

The code snippet is shown below

result=[]
import matplotlib.pyplot as plt
import math
x=list(range(1,11))
defpermutations(iterable, r=None): 
    count=0global result
    pool = tuple(iterable)
    n = len(pool)
    r = n if r isNoneelse r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yieldtuple(pool[i] for i in indices[:r])
    while n:
        for i inreversed(range(r)):
            count+=1
            cycles[i] -= 1if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yieldtuple(pool[i] for i in indices[:r])
                breakelse:
            resulte.append(count)
            returnfor j in x:
    for i in permutations(range(j)):
        continue

x=list(range(1,11))
plt.plot(x,result)

Time Complexity graph for itertools.permutation

From the graph, it is observed that the time complexity is O(n!) where n=Input Size