CODEWITHSUNDEEP
calgorithmtime-complexitycombinationsbinomial-coefficients
Mayur Kharche
Mayur Kharche

Reputation: 717

How to find a sum of the first r binomial coefficients for fixed n?

I have already tried the basic way to solve this series but it takes time for the larger values of n & r. Is there any way to reduce this expression in a single expression whose time complexity doesn't depend on the value of n OR r.Range r,n<=10^5

NOTE: here r < n i.e. i have to find the sum of first r+1 terms of this series.

I have already read this question but it doesn't help me:

Algorithm to find Sum of the first r binomial coefficients for fixed n modulo m

Upvotes: 3

Views: 1883

Answers (2)

user1196549
user1196549

Reputation:

For large N, the binomial coefficients behave like the Gaussian curve (at least for the centermost values). This can be derived from the Stirling formula and is supported by the Central Limit theorem.

Then the partial sum can be approximated by the Error function.

Upvotes: 1

2rd_7
2rd_7

Reputation: 472

AFAIK, there is no such expression to which it can be reduced. But it can be done in O(r) time complexity as follows.

Consider an array A, where A[i] stores nci. Then we can easily verify that A[i] = A[i-1].(n-i+1)/(i)

So 

A[0] = 1;
for(int i=1;i<=r;i++){
    A[i] = A[i-1].(n-i+1)/(i);
}
int ans = 0; //The required answer
for(int i=0;i<=r;i++){
    ans = ans+A[i];
}

Upvotes: 1

Related Questions