- Solve the recurrence relation for computing the binomial coefficients and rewrite the algorithm below with O(n) space efficiency.

Algorithm B(n,k)

//output: C(n,k) value For i <---- 0 to n do for j <--- 0 to min (i, k) do if j = 0 or j = i C [i, j] else C [i, j] <------ C [i - 1, j -1] + C [i -1, j] return C[n, k],