CODEWITHSUNDEEP
algorithmmathbig-ocombinations
templatetypedef
templatetypedef

Reputation: 372942

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

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:

enter image description here

enter image description here

enter image description here

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?

Upvotes: 5

Views: 4505

Answers (3)

agimarco
agimarco

Reputation: 74

The recursion tree shown in the question is wrong according to the algorithm given, it follows the combinationsOf(n-1, k) + combinationsOf(n, k-1) formula, not the combinationsOf(n-1, k) + combinationsOf(n-1, k-1). The one shown here is the correct one:

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

Given this tree, we see that for an (n, k) input the recursion tree has at most the number of nodes given by the recursion tree of the (n, n) input pair.
For a worst-case analysis, we consider the (n, n) input. The height of the tree is n and the number of nodes is 2^n - 1. In the example given we have height 3 and 7 nodes.
The number of recursive calls for the (n, n) input is 2^n - 1 and the worst-case complexity for the algorithm is O(2^n).
The exponential complexity with recursion makes the algorithm unfeasible, even with low n, k values the time cost is too high.

All inputs are (n, k) with n, k positive integers and n>=k.

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183948

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

Upvotes: 6

Strix
Strix

Reputation: 1114

O(2^n)

When n<k you stop the recursion by hitting n=0 after n steps. In each level of recursion you call two functions, so this is where the number 2 came from. If n>k then the recursion in the "right branch" is stopped by hitting k=0 which is fewer steps then hitting n=0, but overall complexity is still 2^n.

But the real problem is the recursion itself - you will hit stack limit really soon.

Upvotes: 4

Related Questions