Argue that $n!$ dominates any polynomial function of $n$, i.e., $n^x = O(n!)$ for any real $x$.

Question

I'm really not sure how to go about proving this. The only way I can think of is by showing how $n^x$ & $O(n!)$ changes when $n = 1, 2, 3,\ldots$.

Any help would be appreciated. Thank you!

Answer 1

Let $ x $ be a real, and let $ n $ be an integer such that $ n\geq 2x $, we have : \begin{aligned} \frac{n^{x}}{n!}&=\frac{n^{x}}{n\left(n-1\right)\cdots\left(n-\left\lfloor x\right\rfloor\right)}\cdot\frac{1}{\left(n-\left\lfloor x\right\rfloor-1\right)!}\\ &\leq\frac{n^{\left\lfloor x\right\rfloor +1}}{n\left(n-1\right)\cdots\left(n-\left\lfloor x\right\rfloor\right)}\cdot\frac{1}{\left(n-\left\lfloor x\right\rfloor-1\right)!}\\ & =\prod_{i=0}^{\left\lfloor x\right\rfloor}{\frac{n}{n-i}}\cdot\frac{1}{\left(n-\left\lfloor x\right\rfloor-1\right)!}\\ &\leq\prod_{i=0}^{\left\lfloor x\right\rfloor}{\frac{2n-2i}{n-i}}\cdot\frac{1}{\left(n-\left\lfloor x\right\rfloor -1\right)!} \ \ \ \ \ \ \ \ \ \ \left(\textrm{Because }\left(\forall i\in\left[\!\left[0,\left\lfloor x\right\rfloor\right]\!\right]\right),\ n\geq 2x\geq 2\left\lfloor x\right\rfloor\geq 2i\right) \\ \frac{n^{x}}{n!}&\leq\frac{2^{\left\lfloor x\right\rfloor }}{\left(n-\left\lfloor x\right\rfloor -1\right)!}\underset{n\to +\infty}{\longrightarrow}0 \end{aligned} Thus : $$ n^{x}=\underset{\overset{n\to +\infty}{}}{\mathcal{o}}\left(n!\right) $$