1
$\begingroup$

I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen within $100$ elements with $0.25$ their probability to appear.

This is the method:

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);  
}

The question is, how many calls to binomial1 would be required to evaluate binomial1(100, 50, 0.25)?

I tried first the fool strategy to implements a system.out.println within the code with an indice increasing each time the algorithm was called. But I realised that it was something fool when I noticed I reached:

passed 2485266 times

Thus I was wondering that as far that the algorithm is called twice every time it is called, I was wondering if it was simply called $2^{100}$ times? Yet, p*binomial1(N-1, k-1, p) seemed to be called only $50$ times with a parameter $k=50$...

I'm only asking for a hint.

$\endgroup$
  • $\begingroup$ Are you looking for a formal analysis here, or for guidance on how to run meaningful experiments? $\endgroup$ – Raphael Dec 16 '15 at 8:51
  • $\begingroup$ a formal analysis of how much this algorithm should be called. $\endgroup$ – ThePassenger Dec 16 '15 at 13:17
  • 2
    $\begingroup$ In that case, check out our reference question. Basically, you'll get a recurrence relation which you then have to solve. Print-line counters will never get you there, but can be useful for forming and testing hypotheses; for instance, do you observe powers of two for small N? $\endgroup$ – Raphael Dec 16 '15 at 14:43
  • $\begingroup$ You don't need a formal analysis to answer the question how often binomal1 is called when you invoke binomial1(100,50). You can write a program to calculate this value. This program must be more efficient than binomial1, e.g. by remembering the values already calculated. $\endgroup$ – miracle173 Dec 21 '15 at 9:08
1
$\begingroup$

Hint1:

Try to figure out by hand the invocations of binomial1 for similar, but smaller numbers, e.g. binomia1l(4,2,p), binomial1(10,5,p), or for not so similar number pairs like binomial1(10,7,p).

Hint2:

You don't need a formal analysis to answer the question how often binomal1 is called when you invoke binomial1(100,50). You can write a program to calculate this value. This program must be more efficient than binomial1, e.g. by remembering the values already calculated.

$\endgroup$
1
$\begingroup$

If we let $T(n,k)$ represent the number of times that binomial1 is called when computing binomial1(n, k, p) we'll have $T(n,k) = T(n-1, k) + T(n-1, k-1)+1$ and $T(-1, k) = T(k, -1) = T(0,0)=1$. The closed form expression for $T(n,k)$ is a bit messy, but fortunately we don't need it.

Note that the binomial coefficients $\binom{n}{k}$ are defined by the nearly similar recurrence $\binom{n-1}{k} + \binom{n-1}{k-1}$ so we'll have $T(n,k)\ge \binom{n}{k}$ and in particular $T(100, 50)\ge \binom{100}{50}$ and by Stirling's approximation we'll have $T(100,50)\approx 2^{100}/\sqrt{50\pi}$, which is pretty much what you guessed.

[In fact, it turns out that $T(n,k)$ is quite a bit larger than $\binom{n}{k}$.]

$\endgroup$
  • 1
    $\begingroup$ that is a very strong hint $\endgroup$ – miracle173 Dec 21 '15 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.