Time-complexity of recursive algorithm for calculating binomial coefficient

Question

I'm studying about algorithm complexity analysis. I have problem with unconformity or C(n, k).

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

How can I determine its execution complexity or T(n)?

Solution

The recurrence you are looking for is

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)       with        T(n,n) = T(n,0) = O(1)

Obviously n is decreased by one every step. If we ignore (just for the moment) that there is a parameter k, basically the number of calls doubles every step. This happens n times, until n = 1. Now C(1,k) returns 1. So you call C(n,k) at most 2ⁿ times. So C(n,k) is in O(2ⁿ).

Now we remember the k. What would be a worst case for k? maybe k = n/2 (for an even n). You can see that you need at least n/2 steps until k reaches 1 or n reaches n/2 in any recursive call. So the number of calls doubles at least 2^n/2 times. But there are many more calls. Writing it down is quite a bit of work.

Edit 1 So lets take a look at this picture

You start calling C(n,n/2) (with n=6). The grey triangle is the part that is contained in the n/2 "steps" until you reach the corner (C(n,0) or C(n,n)) first. But as you can see, there are more calls. I marked the calls, where the recursion stops with a blue box and wrote the number a special C(n,k) is called, with a green number.

Edit 2 The value of C(n,k) and the number of calls of C(n,k), that return the value 1, are the same, since the function return only the value 1 (or a result of a recursive call). In the example you see that the sum of the green numbers written at the blue boxes, which are the number of calls, sums up to 20 which is also the value of C(6,3).

Edit 3 Since all operations in one C(n,k) call run in O(1) (constant time), we only have to count the calls to get the complexity. Notice: If C(n,k) would contain an operation that runs in O(n), we would have to multiply the number of call by O(n) to get the complexity.

You will also notice the connection to Pascal's triangle.

A little trick

The algorithm C(n,k) computes the Binomial coefficient by adding 1's. By using Stirling's approximation you can see, that C(n,n/2) ≈ 2ⁿ/sqrt(n) (left out some constants for simplification). So the algorithm has to add that many 1's and so it has a complexity of O(2ⁿ/sqrt(n)).