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,

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)

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)