Saturday, November 24, 2012

Compute the binomial coefficient in efficient way


C(n, k) = n ! / (n-k) ! k! = n (n-1) ... (n-k+1) / 1. 2. ... (k-1)k

C(n,k) = C(n, n-k) = n! / (n-n +k)! (n-k)!  so we can change r to r-p is r > p-r and keep the operation smaller


for (i = 0; i < k; i++)
{
    res *= (n - i);
    res /= (i+1);
}

O(k) time and (1) space

No comments:

Post a Comment