Proof that $n^\frac{n}{2} \in \mathcal{O}(n!)$

Question

In the context of Algorithm's time complexity, I'm trying to proof the following

$n^\frac{n}{2} \in \mathcal{O}(n!)$

I'm aware of the following inequalities:

$\left(\frac{n}{2}\right)^\frac{n}{2} \leq n! \leq n^n, \quad n\geq1$

but I don't manage to use them to proof the original statement.

Appreciated

Answer 1

We want

$n^\frac{n}{2} \in O(n!) $.

We know that $n! \gt (\frac{n}{e})^n $ so if $n^\frac{n}{2} \le (\frac{n}{e})^n $ for all large enough $n$ we are done.

But this is equivalent to $n^\frac{1}{2} \le \frac{n}{e} $ or $n^{1/2} \ge e $ or $n \ge e^2 $ which is certainly true for $n \ge 9$ since $e < 3$.

This can be used to show that $n^{cn} = O(n!)$ for any $0 < c < 1$.

Note.

$n! \gt (\frac{n}{e})^n $ follows by induction from $(1+\frac1{n})^n < e$ which can be proved in an elementary way by showing that $(1+\frac1{n})^n$ is an increasing sequence which has $e$ as its limit.

Answer 2

By Stirling's approximation, $\ln n! = n \ln n - n + \Theta(\ln n)$

That is, $\exists c_1$ $\hspace{20pt} n \ln n - n + c_1\ln n \leq \ln n!$
That is, $\exists c_1$ $\hspace{20pt} n(\ln n - 1) + c_1\ln n \leq \ln n!$

Let $f(n)=n^{n/2}$

Since $ \hspace{27pt} \ln (f(n)) = n ((\ln n)/2) \leq n(\ln n - 1)$ holds for all $n \geq 8$

We have, $ \hspace{13pt} \ln (f(n)) \leq \ln n! \hspace{20pt}$ for all appropriately large $n$

And thus, $f(n) \in \mathcal{O}(n!)$

Answer 3

Here's an elementary proof that does not require any calculus knowledge.

For even $n$, we can rewrite $n!$, from $1\times2\times\cdots\times n$, as

$$\underbrace{(1n)(2(n-1))(3(n-2))\cdots\left(\frac{n}{2}\left(\frac{n}{2}+1\right)\right)}_{\frac{n}{2}\text{ terms}}$$

As we can see, all of the brackets that are being multiplied are in the form $(1+k)(n-k)$, which we can expand into $n+(n-1)k-k^2=n+k(n-1-k)$. This implies that when $0\leq k\leq n-1$, $(1+k)(n-k)\geq n$. Here, $0\leq k\leq\frac{1}{2}n$, so this condition is satisfied. Hence, we know that

$$n!\geq n^\frac{n}{2}$$

for even $n$.

For odd $n$, we can rewrite $n!$ as

$$\underbrace{(1n)(2(n-1))(3(n-2))\cdots\left(\left(\frac{n-1}{2}\right)\left(\frac{n+3}{2}\right)\right)}_{\frac{n-1}{2}\text{ terms}}\cdot \frac{n+1}{2}$$

Similarly, we can see that each of the pairs of numbers in the brackets is larger than or equal to $n$, so we have

$$n!\geq n^{\frac{n-1}{2}}\cdot\frac{n+1}{2}>n^{\frac{n}{2}}\frac{\sqrt{n}}{2}$$

For $n>4$, we have $\frac{\sqrt{n}}{2}>1$, which imples $n!>n^{\frac{n}{2}}$.

Hence,

$$n^{\frac{n}{2}}\in O(n!)$$