# Time complexity of computing binomial coefficients (with binary representation of integers)

Given two integers $n$ and $k$, I want to compute the exact value of the binomial coefficient ${n \choose k}$.

Here $n$ and $k$ are given in their binary representation, meaning that the size of the input is about $\log n + \log k$.

How fast, in big-O notation, can we compute ${n \choose k}$?

One can compute this in time $O(k)$ using, say, the multiplicative formula (see here). But in the worst case, this is exponential in the size of the input.

Can ${n \choose k}$ be computed faster?

There is no sub-exponential algorithm. For example, $\binom{2n}{n}$ has $\log\binom{2n}{n}$ bits, and according to Stirling's approximation,

$$\binom{2n}{n}=\Theta\left(\frac{2\sqrt{\pi n}\left(\frac{2n}{\mathrm{e}}\right)^{2n}}{\left(\sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^{n}\right)^2}\right)=\Theta\left(\frac{4^n}{\sqrt{n}}\right),$$

we have

\begin{align*} \log\binom{2n}{n}=\Omega(n). \end{align*}

So we need at least $\Omega(n)$ time to output the result of $\binom{2n}{n}$.