How to calculate Binomial Coefficient (nCr) in O(r) time complexity

The binomial coefficient  \binom{n}{r} is the number of ways of picking r outcomes from n possibilities. The value of the binomial coefficient for n and r, where 0 <= r <= n is given by:

\binom{n}{r} = \frac{n!}{(r!)(n-r!)}
Recursive Approach to calculate Binomial Coefficient

Let’s calculate the value of C(n, r) by using the recurrence relation:

\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}
Optimal Substructure
C(n, r) = C(n-1, r-1) + C(n-1, r), where 0 < r <= n
Also,
C(n, n) = 0 & C(n, 0) = 0, for any n >= 0

Recursive Code

//
//  main.cpp
//  Binomial Coefficient (Recursive)
//
//  Created by Himanshu on 01/04/22.
//

#include <iostream>
using namespace std;
 
// Calculate Binomial Coefficient C(n, r)
int calculateBinomialCoeff (int n, int r)
{
    // Base Cases
    if (r > n) {
        return 0;
    }
    
    if (r == 0 || r == n) {
        return 1;
    }
 
    // Recursion
    return calculateBinomialCoeff(n - 1, r - 1)
    + calculateBinomialCoeff(n - 1, r);
}

int main () {
    int n = 8, r = 2;
    
    cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
    
    return 0;
}

Output

C(8, 2) is 28

Time complexity: O(2n)

Understanding the problem in this approach

Here, certain subproblems are recomputed. Let’s see how,

Recursion Tree for C(3, 2)

Recomputations can be avoided by exploiting optimal substructure and overlapping subproblems property and using a Dynamic Programming solution.

Dynamic Programming Approach

We could create a 2d array, C[n][r] in bottom up manner, such that

C[i][j] = C[i-1][j-1] + C[i-1][j]

where C[i][j] = {i \choose j}

Code Implementation (Dynamic Programming Approach)

//
//  main.cpp
//  Binomial Coefficient (Dynamic Programming)
//
//  Created by Himanshu on 31/03/22.
//

#include <iostream>
using namespace std;
typedef long long ll;
 
 // Calculate Binomial Coefficient C(n, r)
ll calculateBinomialCoeff (int n, int r) {
    ll C[n+1][r+1];

    for (int i=0; i<=n; i++) {
        for (int j=0; j<=i && j<=r; j++) {
            // first and last binomial coefficients are
            // always 1
            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][r];
}
 
int main() {
    int n = 8, r = 2;
    
    cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
     
    return 0;
}

Output

C(8, 2) is 28

Time complexity: O(n*r)
Space complexity: O(n*r)

Also read:

Optimal space and time complexity approach

We know that,
C(n, r) = \frac{n!}{(r!)(n-r!)}

Simplifying C(n, r)
=  \frac{n!}{(r!)(n-r!)} 
=  \frac{n * (n-1) *....* 1}{( r * (r-1) * .... * 1 ) * ((n-r) * (n-r-1) * .... * 1)} 

Cancelling factors between numerator and denominator, we get:

=  \frac{n * (n-1) *....* (n-r+1)}{( r * (r-1) * .... * 1 ) } 

Also, C(n, r) = C(n, n-r). So we would use C(n, min(r, n-r)) to calculate  binomial coefficient

Code Implementation

//
//  main.cpp
//  Binomial Coefficient (Efficient)
//
//  Created by Himanshu on 01/04/22.
//

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
 
 // Calculate Binomial Coefficient C(n, r)
ll calculateBinomialCoeff (int n, int r) {
    ll binomialCoeff = 1;
    
    if (n < r) {
        return -1;
    }
    
    r = min(r, n-r);
    
    for (ll i=n; i>n-r; i--) {
        binomialCoeff = binomialCoeff*i;
        binomialCoeff = binomialCoeff/(n-i+1);
    }

    return binomialCoeff;
}
 
int main() {
    int n = 8, r = 2;
    
    cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
     
    return 0;
}

Output

C(8, 2) is 28

Time complexity: O(r)
Space complexity: O(1)

Leave a Reply

Your email address will not be published.