From Algorithm Design and Applications ISBN: 9781118335918 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 choices or combinations. In this case, the definition is as follows:

and, for 0 < k < n,

C (n, 0) = 1, C (n, n) = 1,

C (n, k) = C (n 1, k 1) + C (n 1, k)

(a) Show that, if we dont use memoization, and n is even, then the running time for computing n n

C n,2 isatleast22 (b) Describe a scheme for computing C (n, k) using memoization. Give a big-oh character-

ization of the number of arithmetic operations needed for computing C n,n in this 2

case.