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: 

(a) Show that, if we don’t use memoization, and n is even, then the running time for computing C(n, n/2) is at least 2n/2. 

(b) Describe a scheme for computing C(n, k) using memoization. Give a bigoh characterization of the number of arithmetic operations needed for computing C(n, [n/2]) in this case.

Transcribed Image Text:

C(n, 0) = 1, C(n, n) = 1, and, for 0 < k