What is the time complexity of this binomial coefficient algorithm? Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$:

def coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return coefficient(n-1, k-1) + coefficient(n-1, k)


Now the time complexity has to be bounded by $2^n$, however we have to take $k$ into account. The best cases are when k = 0 or k = n. So, with k and n decrementing, we get the most branching when $k = \frac{n}2$.

I'm looking for the worst case time complexity. I can write the recurrence relation, but I don't know how to go from here:

$T(n,k) = T(n-1, k-1) + T(n-1, k) + constant$
The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.

Now prove it.