Is the complexity of $\binom{2n}{n} = O(2^n)$? 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!$
 A: 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.
A: 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*}$
