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

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

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

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.