Binomial Coefficients
Computes C(n, k) — "n choose k" — with the multiplicative formula, multiplying and dividing incrementally instead of computing three large factorials that could overflow.
- Category
- Mathematics
- Time complexity
- O(k)
- Space complexity
- O(1)
Pseudocode
result ← 1 for i in 0..k−1 result ← result × (n−i) / (i+1) result = C(n, k)
Reference implementation
def choose(n, k):
result = 1
for i in range(k):
result = result * (n - i) // (i + 1)
return result