这个天真的代码计算组合的big-O复杂度是多少？

`````` 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);
}
``````

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

lillo
``````O(2^n)
``````

luyao

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

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

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

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

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

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