1
$\begingroup$

How to estimate the number of recursive calls that would be used by the code

public static double binomial(int N, int k, double p) { if ((N == 0) || (k < 0)) return 1.0; return (1.0 - p)*binomial(N-1, k) + p*binomial(N-1, k-1);  } 

to compute binomial(100, 50)???

I am looking for the formula that gives me the exact number of calls I think it is related to factorial but I can't find formula

number of recursive calls for $n\leq 6$

$(1,0)=3$
$(2,0)=5$
$(2,1)=7$
$(3,0)=7$
$(3,1)=13$
$(3,2)=15$
$(4,0)=9$
$(4,1)=21$
$(4,2)=29$
$(4,3)=31$
$(5,0)=11$
$(5,1)=31$
$(5,2)=51$
$(5,3)=61$
$(5,4)=63$
$(6,0)=13$
$(6,1)=43$
$(6,2)=83$
$(6,3)=113$
$(6,4)=125$
$(6,5)=127$

  • 0
    I hope you're not going to use this algorithm in real life?2012-12-11
  • 0
    Assuming you are using Java, add a global variable. `public static int counter;`2012-12-11
  • 0
    I calculated this numbers with java but it is very big number and takes hours to find it. I am sure that there is number and I think formula is like this 2*n+X+1 but can't find X2012-12-11
  • 0
    You have gotten the answer in several of the other forums where you posted this question.2012-12-11
  • 0
    Maybe post it on stackoverflow2012-12-11
  • 0
    It's suspicious that you don't get the same value, e.g., for $(4,1)$ and $(4,3)$, and that you don't compute $(4,4)$. Looking at the implementation, it appears to be getting the base cases severely wrong, although it's not clear exactly what you're trying to compute.... Also, the arguments to the definition of `binomial` don't match the arguments you're passing into the recursive calls.2013-01-13

1 Answers 1