Introduction

Binomial coefficients are mathematical entities that arise in combinatorics, probability theory, and algebra. The binomial coefficient n choose k represents the number of ways to choose k elements from a set of n elements without regard to order. The algorithm we will discuss computes the binomial coefficient using a combinatorial formula that iteratively multiplies the numerator by n - i and the denominator by i + 1, starting from 1 and going up to the smaller of k and n - k.

Implementation


(* Evaluate binomial coefficients *)

let binomialCoeff n p =
  let p = if p < n -. p then p else n -. p in
  let rec cm res num denum =
    if denum <= p then cm ((res *. num) /. denum) (num -. 1.) (denum +. 1.)
    else res in
  cm 1. n 1.

The binomial coefficient algorithm takes two arguments: n and p. It calculates the binomial coefficient of n and p. It first computes the minimum of p and n - p, then initializes variables res, num, and denum and passes them to a helper function cm.

cm takes a result res, a numerator num, and a denominator denum and iteratively multiplies res by num and divides by denum, decrementing num and incrementing denum until denum is greater than p. The final result of cm is the binomial coefficient of n and p.

Step-by-step Explanation

  1. Check if p is greater than n - p. If it is, set p to n - p to reduce the number of computations. This is because n choose k is equivalent to n choose n-k, and k must be no greater than n / 2.

  2. Initialize a result variable res to 1, a numerator variable num to n, and a denominator variable denum to 1.

  3. Pass res, num, and denum to a helper function cm.

  4. In cm, calculate res * num / denum and assign to res.

  5. Decrement num by 1 and increment denum by 1.

  6. If denum is less than or equal to p, recurse by calling cm with res, num, and denum as arguments.

  7. If denum is greater than p, return res as the binomial coefficient of n and p.

Complexity Analysis

The algorithm performs a constant amount of initialization before calling the helper function cm. The helper function cm performs p iterations, each of which performs one multiplication and one division. Therefore, the time complexity of the algorithm is O(p), where p is the smaller of p and n - p.

The space complexity of the algorithm is O(1), as it only initializes a constant number of variables regardless of the input size.