Comparing the grow rate of two functions with discrete domain Consider all the possible ways to put $\{0,1\}$ in $m\in \mathbb{N}$ places. E.g., if $m=3$, then the number of possibilities is $8$
$$
\begin{pmatrix}
1 & 1 & 1\\
1 & 1 & 0\\
1 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 1\\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0\\
\end{pmatrix}
$$
Fix any $j\in \{0,2,...,m\}$. I am interested in the number of rows of the matrix above giving $j$ as sum. 
E.g., for $j=2$, I have $3$ rows (second, third, fourth). 
I found that this number can be calculated as 
$$
\frac{m!}{j!(m-j)!}
$$ 
For any fixed value of $m$, the function $f_m$ such that $j\in \{0,1,...,m\}\mapsto f(j)\equiv \frac{m!}{j!(m-j)!}$ is firstly increasing, then hits its  maximum, then it becomes decreasing. The picture below represents $f_m$ for $m=3,...,9$.
Now, take the functions


*

*$g$ such that $m\in \mathbb{N}\mapsto g(m)\equiv \max_{j\in \{0,...,m\}}f_m(j)$. 

*$h$ such that $m\in \mathbb{N}\mapsto h(m)\equiv 2^{m}$. 
Question: what is the growth rate in Big O notation of $g$? what is the growth rate in Big O notation of $h$? How do they compare?
 A: $\displaystyle \frac{m!}{j!(m-j)!}$ is commonly referred to as a binomial coefficient and usually writen as $\binom{m}{j}$.
Note that $\displaystyle \frac{\binom{m}{j}}{\binom{m}{j-1}} = \frac{m-j+1}{j}$, thus $\binom{m}{j}$ increases strictly so long as $$\frac{m-j+1}{j} > 1\iff m\geq 2j\iff \lfloor \frac m2 \rfloor\geq j$$
Thus $\displaystyle g(m)= \binom{m}{\lfloor \frac m2 \rfloor}$. If $m$ is even, write $m=2k$ and $\binom{m}{\lfloor \frac m2 \rfloor} = \binom{2k}{k}$. Going back to factorials, Stirling's estimate (see this or that) yields $\displaystyle \binom{2k}{k}\sim \frac{2^{2k}}{\sqrt{\pi k}}$.
If $m$ is odd, write $m=2k+1$, so that $\binom{m}{\lfloor \frac m2 \rfloor} = \binom{2k+1}{k} = \binom{2k+1}{k+1}=\frac{2k+1}{k+1}\binom{2k}{k}$. Using the previous estimate, $\displaystyle \frac{2k+1}{k+1}\binom{2k}{k}\sim \frac{2^{2k+1}}{\sqrt{\pi k}}$.
Therefore $$g(m) \sim \frac{2^m}{\sqrt{\pi \lfloor \frac m2 \rfloor}}$$
Since $\displaystyle \lfloor \frac m2 \rfloor = \frac m2 +O(1)$, $\displaystyle \lfloor \frac m2 \rfloor \sim \frac m2$ thus 
$$g(m) \sim \sqrt{\frac{2}{\pi}}\frac{2^m}{\sqrt{m}} = o(h(m))$$
