current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise
up vote 1 down vote favorite
2

I'm working through the fourth edition of Algorithms by Robert Sedgewick and Kevin Wayne and am stumped on exercise 1.1.27 which asks:

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) + p*binomial(N-1, k-1, p);
}

to compute binomial(100, 50).

Although I'd like like help answering this question, I'd also like to get better at understanding and reasoning about questions of this nature in general and so any help or pointers would be appreciated.

share|improve this question
    
What's the initial value of p, assumed 0? – lurker May 26 '13 at 18:00
4  
You should read what some of the old mathematicians and scientists did. They used to record pages and pages of raw calculations that they did by hand. Some people would write the first 500 members of a sequence to get an idea of the properties of some sequence with the goal that that would help them prove some property. The same applies here... did you try plugging in some values and writing out the number of recursive calls by hand? Nowadays you could modify the code slightly and have a computer tell you; but there's no real harm in doing it on paper – rliu May 26 '13 at 18:02
1  
@mbratch The exercise in its entirety is in my question but I don't think it matters anyway as it has no effect on the recursive properties of the function – Simon Morgan May 26 '13 at 18:06
    
@roliu Thanks. I'm doing that now in a diagram editor (I'm making a tree structure) but I'm really looking for help at getting better at reasoning about these kinds of things. – Simon Morgan May 26 '13 at 18:09
1  
Modulo a small difference at the base cases, the recursion is the same as here. – Daniel Fischer May 26 '13 at 18:57
up vote 5 down vote accepted

This algorithm traverses Pascal's triangle.

You can arrange the triangle traversal as a rectangle N * K. If the algorithm visits every cell only once, then total is 100 * 50 = 5000.

Here is an example:

Pascal's Triangle with rectangle

In this example N=6 and K=4.

However, the problem is that the algorithm does not remember what cells it already visited so it is redundantly visiting cells. Each call DOUBLES the number of calls (oops, bad).

So it goes 1 + 2 + 4 + 8 + 16 + 32 + ...

The sum of powers of 2 is 2^(n+1)-1, so it would be 2^101 - 1 = 2535301200456458802993406410751

That is a big number. Do not run this program.

(Note that the number is only approximate because some calls do not double if K<0, so it may the above number divided by 2 or so).

share|improve this answer
    
I think it grows much faster than Pascal's because there are many redundant recursive calls. For instance (3,2) results in 12 calls. – rliu May 26 '13 at 18:42
    
That is true, it is not memoized so it redundantly visits cells. – Tyler Durden May 26 '13 at 18:56
up vote 1 down vote

You'll see the pattern right away if you start with concrete examples. For N=0, obviously it's 0. For N=1, it's 2 recursive calls (because each call yields two recursive call at the directly inferior level, i.e. for N-1.

For N=2, then it's 2*2 = 4

For N=3, then it's 2*2*2 (i.e. 2^3)

For N=4, then it's 2^4

I'm assuming you see the pattern.

share|improve this answer
    
What about the cases where k is less than N? – Simon Morgan May 26 '13 at 18:40
    
(k < 0) this condition come first. so 2^50. – Daedelus May 31 '13 at 14:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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