C-12.1 Binomial coefficients are a family of positive integers that have a number of useful properties and they can be defined in several ways. One way to define them is as an indexed recursive function, C (n, k), where the "C" stands for "choice" or "combinations." In this case, the definition is as follows: C (n, 0) = 1, C (n, n) = 1, and, for 0

Step-by-step explanation:

a)

If we implement the combinations recursively without memoization, then the running time would be exponential in n.

Time Complexity:

If we implement this equation literally, as a recursive program, then the running

time of our algorithm without using memoization, T (n), as a function of n, has the following behavior:

T (0) = 1

T (1) = 1

T (n) = T (n - 1) + T (n - 2).

But this implies that

T (n) ≥ 2T (n - 2) = 2^ (n/2).

b)

But if we store the combinations in an array, C[][], then we can instead calculate the combinations, C (n, k), iteratively, as follows:

C[0,0] = 0

C[1,1] = 1

for i = 2 to n do

C[n, k] = C[n-1, i-1] + C[n-1, k]

This algorithm clearly runs in O (n) time, and it illustrates the way memoization

can lead to improved performance when subproblems overlap and we use table

lookups to avoid repeating recursive calls.