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!$

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