https://docs.python.org/3/library/math.html#math.comb
This is a nice convenient function for solving n choose k problems, without having to build from scratch. Does anyone know the time complexity of this specific method? Is it O(n choose k) as described in this question?
What's time complexity of this algorithm for finding all combinations?
Is there any optimization involved in the implementation of math.comb() that reduces the time complexity to less than O(n choose k)?
I believe it is 2N, if you look at the manual code of nCr then you'll notice One while loop for factorial(n), one for factorial (r) and one more for factorial (n-r).
So the while loops for calculating factorials of r and n-r are equivalent to factorial (n).
So basically it is running 2N times but, if you modify the code to store the fact(r) and fact(n-r) in a single loop while finding fact(n). Then maybe it can be O(N).
I don't have a definitive answer, but math.comb() seems to be on the slow side:
Was using math.comb() to solve a Pascal Triangle problem:
from math import comb
def get_row(k):
row = [None for _ in range(k+1)]
row[0], row[-1] = 1, 1
for y in range(1, k):
row[y] = comb(k, y)
return row