3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.