Is the complexity of $\binom{2n}{n} = O(2^n)$?

Question

How to find the complexity of $f(n)=\binom{2n}{n}$?

We know that $f(n)=\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$.

Is this $O(n^2)$? What concerns me is $n!$

Answer 1

First off, you know that:

$\begin{align*} 2^{2 n} &= (1 + 1)^{2 n} \\ &= \sum_{0 \le k \le 2 n} \binom{2 n}{k} \\ &\ge \binom{2 n}{n} \end{align*}$

so that $\binom{2 n}{n} = O(2^{2 n})$.

More precise estimates are from Stirling's approximation, in the variant given by Robbins ("A Remark on Stirling's Formula", AMM 62:1 (1955), 26-29):

$\begin{align*} &n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \cdot e^{r(n)} \\ &\frac{1}{12 n + 1} < r(n) < \frac{1}{12 n} \end{align*}$

We have:

$\begin{align*} \binom{2 n}{n} &= \frac{(2 n)!}{(n!)^2} \\ &= \frac{1}{\sqrt{\pi n}}\cdot 2^{2 n} \cdot e^{r(2 n) - 2 r(n)} \\ \end{align*}$

This means that:

$\begin{align*} \binom{2 n}{n} = \Theta\left(2^{2 n} \cdot n^{-1/2}\right) \end{align*}$

Answer 2

The OEIS sequence A000984 "Central binomial coefficients" contains the line

Using Stirling's formula in $A000142$ it is easy to get the asymptotic expression $a(n) \sim 4^n / \sqrt{\pi n}.$

which implies that $a(n) := \binom{2n}{n} = O(4^n).$ The Wikipedia article Central binomial coefficient has this expression also using Stirling's approximation formula and this implies that the sequence is not of polynomial growth rate.