Compute binomial coefficient
  • recursion
  • binomial
  • dynamicprogramming
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2271)

Write a recursive function to compute the binomial coefficient \( C(n,k) \) of given two parameters \( n \) and \( k \).


Posted Answers

The binomial coefficient \( C(n,k) \) can be recursively computed as \( C(n,k) = C(n-1,k-1)+C(n-1,k) \), \( C(n,0) = C(n,n)=1 \)

int CompBinomialCoefficient(int n, int k){
/* Base case */
if(k == 0 || k == n)
return 1;
else
return CompBinomialCoefficient(n-1,k-1) + CompBinomialCoefficient(n-1,k);
}

Since some sub problems are called more than once, we can use dynamic programming. Re-computation of same problem can be avoided by constructing a temporary \( 2d \) array in \( bottom \) - \( up \) manner.

int CompBinomialCoefficient(int n, int k){
int C[n+1][k+1];

for(int i = 0; i < = n; i++){
for(int j = 0; j < = min(i,k); j++){
/* Base case */
if(j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}

Time complexity = \( O(nk) \).

You need to Sign In to post your solution.