Question

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

Answer 1

Answer:

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.