wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Inefficent Binomial Computation
        
(Message started by: Barukh on Oct 16^th, 2003, 6:48am)

Title: Inefficent Binomial Computation
Post by Barukh on Oct 16^th, 2003, 6:48am

Consider the following code for computing the binomial coefficients:

Code:

int C(int n, k)
{
if (n == 0) || (k == n) return 1;
else return C(n-1, k) + C(n-1, k-1);
}

This function is very inefficient since it computes the same values over and over again. The question is: exactly, how many times the function is called to compute _nC_k (n-choose-k)?

Title: Re: Inefficent Binomial Computation
Post by James Fingas on Oct 17^th, 2003, 10:10am

It seems to take [hide]2*C(n,k)-1[/hide] calls. This is relatively easily shown below:
[hide]
We ignore for the moment the initial function call with parameters n,k. For n=0 or k=n, we therefore take zero function calls.

By examining the function, the number of function calls N(n,k) (without the initial call) is equal to 2 plus the number of fuction calls N(n-1,k) and N(n-1, k-1). This is different from the recursion relation for Pascal's triangle. However, when we add one to all values in the triangle, the recursion relation becomes [N(n,k) + 1] = 1 + [N(n-1,k) + 1] + [N(n-1,k-1) + 1], and when we add another to all values in the triangle, we get the recursion [N(n,k) + 2] = [N(n-1,k) + 2] + [N(n-1,k-1) + 2], the relation from Pascal's triangle. The difference is that the values at the edges are 2 instead of 1, so [N(n,k) + 2] is C(n,k)*2.

The number of function calls including the initial call is N(n,k) + 1 = 2*C(n,k) - 1.[/hide]

Title: Re: Inefficent Binomial Computation
Post by Barukh on Oct 18^th, 2003, 12:50am

James, your answer is correct and the solution interesting. When I was challenged with this question, I arrived at the following solution
[smiley=blacksquare.gif]
[hide]The process of computing C(n,k) may be represented as a binary tree, which terminal nodes correspond to 'if' condition, and internal nodes to 'else' condition. Since every terminal node contributes 1, there are C(n,k) of them.

Now, it remains to recall the well-known fact: in any binary tree, the number of internal nodes is the number of terminal nodes - 1.
[/hide][smiley=blacksquare.gif]