Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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}$.
