Question: Consider the subsequent algorithm to compute binomial coefficients.
function C(n,k)
if k = 0 or k = n then return 1
else return C(n-1, k-1) + C(n - 1, k)
Analyze the time taken by this algorithm under the unreasonable assumption that the addition C(n-1, k-1) + C(n - 1, k) can be carried out in constant time once both C(n-1, k-1) and C(n - 1, k) have been obtained recursively.
Let t(n) show the worst time that a call on C(n,k) may take for all possible values of k, 0 ≤ k ≤ n. Express t(n) in the simplest possible form in
You have to satisfy the requirements specific in the instruction.