8

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

7
  • 2
    Step 1: write a recurrence. Commented Oct 7, 2014 at 4:08
  • Sorry, I don't understand, can you say it more clearly
    – Andiana
    Commented Oct 7, 2014 at 4:16
  • I mean, write equations for T(n, k) such that T(n, k) is big-Theta of the running time of C(n, k). Commented Oct 7, 2014 at 4:17
  • I think T(n) is:if(n==
    – Andiana
    Commented Oct 7, 2014 at 4:20
  • 1
    I think you mean if(n==k || k==0)? The 0 is missing. Commented Oct 7, 2014 at 5:56

1 Answer 1

25

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

13
  • I understood until "need at least n/2 steps until k reaches 1 or n reaches n/2", but I think, after n/2 step (at most), k must reach 1 or n much reach k, so the max steps number must be n/2 (instead of at least n/2)? Can you tell me more clearly? And is 1's is 1 step? And why we have C(n, n/2) in complexity?
    – Andiana
    Commented Oct 7, 2014 at 14:55
  • 1
    @HyNguyen I improved my answer a little bit. Commented Oct 7, 2014 at 15:35
  • It's took me a time to digest it :) So why we calc the complexity of C(n, k) through C(n, n/2), is it the max complexity?
    – Andiana
    Commented Oct 8, 2014 at 0:50
  • yes, C(n,n/2) is the worst case. In complexity theory and specialy in big O you are interested in worst case complexity. Since C(n,k) is symmetric, C(n,n/2) is the worst case. Commented Oct 8, 2014 at 0:55
  • 1
    @PanosK. I used Illustrator. Commented Aug 11, 2017 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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