# How to improve the binomial algorithm?

Good evening!

I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form:

$$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$$

Then, tried to estimate the number of recursive calls that would be used by the method call binomial1(100, 50, .25)

public class Binomial {

public static double binomial1(int N, int k, double p) {
if (N == 0 && k == 0) return 1.0;
if (N < 0 || k < 0) return 0.0;
return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
}
public static void main(String[] args) {
int N = Integer.parseInt(args);
int k = Integer.parseInt(args);
double p = Double.parseDouble(args);
StdOut.println(binomial1(N, k, p));
StdOut.println(binomial2(N, k, p));
}

}


I think I have $2^N$ recursive calls of binomial1, that is to say 10000 calls with our exemple. Because of this line:

return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);


I would like to explain it better... I think my answer is too intuitive: each time I call the algorithm, I call it twice until N reach 0.

How to improve with an implementation that would be based on saving computed values in an array?

• What is your question? How to calculate the probability that a binomial random variable $B(n,p)$ equals $k$? Please try to explain yourself better. Also, please replace your C++/Java code with pseudocode. Oct 24, 2015 at 19:08
• The binomial coefficient is really $$\binom{n}{k} = \frac{n^{\underline{k}}}{k!}$$, where $x^{\underline{k}} = x (x - 1) \dotsm (x - k + 1)$, which gives you the nice recursion $$\binom{n}{k + 1} = \binom{n}{k} \cdot \frac{n - k}{k + 1}$$ Oct 25, 2015 at 0:33
• I don't understand the formula in context of the code. It seems to me that the answer is "compute $(x+y)^n$ directly".
– Raphael
Oct 26, 2015 at 7:35
• @Raphael The program itself reads $n,k,p$ as input and outputs $\binom{n}{k} p^k (1-p)^{n-k}$. But it looks like an exercise in dynamic programming. Oct 26, 2015 at 7:43
• If this code runs and compiles without error you can post it on codereview and ask for hints to improve this code. Dec 21, 2015 at 16:37

The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

For completeness, here are the formula and the recursion: $$\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}.$$

There are many ways to use memoization here. One natural way is to loop on n, and compute all values of binomial1 in sequence. This only requires knowing the values of binomial1 on n-1, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given k.

I'll let you come up with matching code and runtime analysis.

• "memoization (sometimes known as dynamic programming)" -- obligatory note for the reader: some people use these terms as though they were synonyms, but they are not.
– Raphael
Oct 26, 2015 at 7:35
• Another hint: the binomial coefficients are symmetric.
– Raphael
Oct 26, 2015 at 7:36