Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time-complexity of recursive algorithm for calculating binomial coefficient

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)?

like image 408
Andiana Avatar asked Oct 07 '14 04:10

Andiana


People also ask

What is the time complexity of the binomial coefficient algorithm?

Thus, the overall time complexity for evaluating M binomial coefficients C(P, Q) modulo 2N with 0 ≤ Q ≤ P ≤ 2N − 1 is O((N 3 + M · N 2 · log(N)) · Multiplication(N) + N 4).

What is complexity of binomial coefficient using dynamic programming?

Time complexity: O(2n)

What is the time complexity of recursive power function?

Time Complexity: O(N) because pow(x,n) is called recursively for each number from 1 to n.


1 Answers

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 2n times. So C(n,k) is in O(2n).

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 2n/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

pascal's triangle with number of calls and arrows

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) ≈ 2n/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(2n/sqrt(n)).

like image 170
AbcAeffchen Avatar answered Nov 15 '22 22:11

AbcAeffchen