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?