algorithm - What is the big-O complexity of this naive code to compute combinations?

Question

The following recursive algorithm is a (fairly inefficient) way to compute n choose k:

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

It is based on the following recursive insight:

Actually evaluating this function takes a LOT of function calls. For example, computing 2 choose 2 this way makes these calls:

 combinationsOf(2, 2)
   |  |
   |  +- combinationsOf(1, 2)
   |       |  |
   |       |  +- combinationsOf(0, 2)
   |       |
   |       +-- combinationsOf(1, 1)
   |             |  |
   |             |  +- combinationsOf(0, 1)
   |             |
   |             +- combinationsOf(1, 0)
   +- combinationsOf(2, 1)
        |  |
        |  +- combinationsOf(2, 0)
        |
        +- combinationsOf(1, 1)
             |  |
             |  +- combinationsOf(0, 1)
             |
             +- combinationsOf(1, 0)

There are many ways to improve the runtime of this function - we could use dynamic programming, use the closed-form formula nCk = n! / (k! (n - k)!), etc. However, I am curious just how inefficient this particular algorithm is.

What is the big-O time complexity of this function, as a function of n and k?

Answer 1

Let C(n,k) be the cost of computing binom(n,k) in that way, with

C(0,_) = 1
C(_,0) = 1

as base cases.

The recurrence is obviously

C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)

if we take addition to have cost 1. Then, we can easily check that

             k
C(n,k) = 2 * ∑ binom(n,j) - 1
            j=0

by induction.

So for k >= n, the cost is 2^(n+1) - 1, C(n,n-1) = 2^(n+1)- 3, C(n,1) = 2*n+1, C(n,2) = n*(n+1)+1, (and beyond that, I don't see neat formulae).

We have the obvious upper bound of

C(n,k) < 2^(n+1)

independent of k, and for k < n/2 we can coarsely estimate

C(n,k) <= 2*(k+1)*binom(n,k)

which gives a much smaller bound for small k, so overall

C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})

(need to clamp the k for the minimum, since binom(n,k) decreases back to 1 for k > n/2).