# What is the complexity of computing \$C(n + m, m)\$?

According to Pascal identity,(suppose $$kleq n$$)

$$binom{n}{k}=binom{n-1}{k-1}+binom{n-1}{k}$$
That give us a recurrence relation to find value $$binom{n}{k}$$.

Unfortunately, above recurrence to find value $$binom{n}{k}$$ ,without memoization ( or dynamic programming methods),needs time complexity
$$Thetaleft(2^{n}right).$$ on the other hand, with dynamic programming,
the running time is
$$Omega(n).$$

So you can’t compute $$binom{n}{k}$$ in $$min(n,k)$$ time. Because $$binom{n}{k}$$ have $$logbinom{n}{k}$$ bits,so you need at least write or read $$Omega(n)$$ bits.