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$