Author |
Topic: Inefficent Binomial Computation (Read 1025 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Inefficent Binomial Computation
« on: Oct 16th, 2003, 6:48am » |
 Quote  Modify
|
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 nCk (n-choose-k)?
|
|
 IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Inefficent Binomial Computation
« Reply #1 on: Oct 17th, 2003, 10:10am » |
Quote Modify
|
It seems to take 2*C(n,k)-1 calls. This is relatively easily shown below:
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Inefficent Binomial Computation
« Reply #2 on: Oct 18th, 2003, 12:50am » |
Quote Modify
|
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]
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.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print