December 1st, 2012, 06:16 PM

Calculate recursive calls number
How I can estimate the number of recursive calls that would be used by the code
Code:
public static double binomial(int N, int k, double p)
{
if ((N == 0)  (k < 0)) return 1.0;
return (1.0  p)*binomial(N1, k) + p*binomial(N1, k1);
}
to compute binomial(100, 50)?
I am looking for the formula that gives me the exact number of calls
dont wanna to do it with a counter because the number is very very big and it takes time to calculate
I'm sure there is a formula
December 1st, 2012, 09:01 PM

If f(N,k) is the number of recursive calls made by binomial(N,k,p), then:
 f(0,k) = f(N,0) = 0 (basis case: no recursive calls)
 f(N,k) = 2 + f(N,k1) + f(N1,k1) if N >= 0 and k >= 0 (two recursive calls, plus however many recursive calls they make)
Make a table of the values for small values of N and k, and hopefully, you'll see a pattern. (Hint: the function g(N,k) = f(N,k)/2 + 1 satisfies a simpler recurrence than f(N,k). Are you familiar with Pascal's triangle?)
December 2nd, 2012, 06:48 AM

Originally Posted by Lux Perpetua
If f(N,k) is the number of recursive calls made by binomial(N,k,p), then:
 f(0,k) = f(N,0) = 0 (basis case: no recursive calls)
 f(N,k) = 2 + f(N,k1) + f(N1,k1) if N >= 0 and k >= 0 (two recursive calls, plus however many recursive calls they make)
Make a table of the values for small values of N and k, and hopefully, you'll see a pattern. (Hint: the function g(N,k) = f(N,k)/2 + 1 satisfies a simpler recurrence than f(N,k). Are you familiar with Pascal's triangle?)
I think your answer is not true because if f(N,k) is the number of recursive calls it should be like this
f(N,k)=f(N1,k)+f(N1,k1)+1
I know this formula but I want to find the formula to calculate the f(100,50) or something like that
this is the table of value for N<6
Code:
(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
(7,0)=15
(7,1)=57
(7,2)=127
(7,3)=197
(7,4)=239
(7,5)=253
(7,6)=255
(8,0)=17
(8,1)=73
(8,2)=185
(8,3)=325
(8,4)=437
(8,5)=493
(8,6)=509
(8,7)=511
(numbers is recursive calls numbers)
I couldn't find anything from this numbers
December 2nd, 2012, 12:37 PM

Originally Posted by arira
I think your answer is not true
because if f(N,k) is the number of recursive calls it should be like this
f(N,k)=f(N1,k)+f(N1,k1)+1
I interpreted the problem differently than you: in your formula, toplevel calls count as recursive calls, while in mine, they do not. No big deal. Also, I see that I misread "k < 0" as "k <= 0" in your code, which does change the formula.
Look at f(N,k)  f(N,k1), and hopefully you'll notice the pattern. Also, arrange the table like this:
Code:
(0,1) (0,0) (0,1) (0,2) (0,3)
(1,1) (1,0) (1,1) (1,2) (1,3)
(2,1) (2,0) (2,1) (2,2) (2,3) (etc.)
(3,1) (3,0) (3,1) (3,2) (3,3)
(etc.)
December 2nd, 2012, 05:44 PM

Originally Posted by Lux Perpetua
I interpreted the problem differently than you: in your formula, toplevel calls count as recursive calls, while in mine, they do not. No big deal. Also, I see that I misread "k < 0" as "k <= 0" in your code, which does change the formula.
Look at f(N,k)  f(N,k1), and hopefully you'll notice the pattern. Also, arrange the table like this:
Code:
(0,1) (0,0) (0,1) (0,2) (0,3)
(1,1) (1,0) (1,1) (1,2) (1,3)
(2,1) (2,0) (2,1) (2,2) (2,3) (etc.)
(3,1) (3,0) (3,1) (3,2) (3,3)
(etc.)
I tried every thing for 3 day
searched in the net and ask everyone I know
now I think maybe there is not a formula
December 2nd, 2012, 08:28 PM

There is definitely a formula. Do you not see a pattern after writing f(N,k)  f(N,k1) in the grid like I said and comparing it to Pascal's Triangle?
I've all but written down the answer for you at this point. Of course, I could be wrong, like I was wrong before, but I think it's more likely that you're not following my hints. Also, if you've really been trying this for three days with no success, then the law of diminishing returns probably applies. After a while, spending additional time banging one's head against a problem doesn't pay off. Sometimes stepping away for a while can help.
December 3rd, 2012, 04:05 AM

Originally Posted by Lux Perpetua
There is definitely a formula. Do you not see a pattern after writing f(N,k)  f(N,k1) in the grid like I said and comparing it to Pascal's Triangle?
I've all but written down the answer for you at this point. Of course, I could be wrong, like I was wrong before, but I think it's more likely that you're not following my hints. Also, if you've really been trying this for three days with no success, then the law of diminishing returns probably applies. After a while, spending additional time banging one's head against a problem doesn't pay off. Sometimes stepping away for a while can help.
I did what you said
but I couldn't find the relationship between the numbers after spending 3 days and asking all of my friends. I have another works to do so I give up. maybe you are right and I should leave this problem ,do another things and after few days try it again.
thanks for your help
December 6th, 2012, 06:15 AM

I sent an email to writer of the book that I found this problem in it and he answered me:
Hint: calculate the number of calls for some small values of N and k and consider functions that involve N! (N factorial) and k! (k factorial).
does anyone have any idea?
December 11th, 2012, 01:49 AM

Interesting question to which, unfortunately at the moment, I don't know the answer. One thing though is that all your computed number of calls are out by 1 i.e.:
let a = 1, b = 1
g(a,b) => g(1,1) => #1
g(a, b1) => g(1, 0) => #2 + g(a1, b) => g(0, 1) => #3
December 11th, 2012, 06:50 AM

I think formula is something like 2*n+X+1
it works if k=0
(1,0)=2*1+1=3
(2,0)=2*2+1=5
(5,0)=2*5+1=11
but when k is not zero it is different and I think X is related to k
January 4th, 2013, 08:41 PM

woman affiliated applause to grab for their Franch men pk Louis vuitton Bags
Tiffany & Co Outlet
Tiffany & Co Bracelets
Tiffany & Co Jewelry
Karen Millen Dress
Doudoune Moncler Pas Cher
Comments on this post
March 5th, 2013, 12:45 AM

Actually i dont know how to calculate this one.But really its very interesting.