How to improve the binomial algorithm?

Question

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[0]);
        int k = Integer.parseInt(args[1]);
        double p = Double.parseDouble(args[2]);
        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?

Answer 1

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.