# big o notation / asymptotic for factorial

I want to write $g(x)=x!\cdot(x^4-1)$ in the big O notation $g\in \mathrm O(???)$ for $x\rightarrow\infty$.

But I have no idea how to do this.

Thanks for helping!

-
There is no "the" which will fill the $???$ in $O(???)$. –  Aryabhata Apr 26 '12 at 7:52
Well, clearly $???=x^{x+4}$ would work. A more useful asymptotic would come from Stirling's formula. What are you looking for more specifically? –  anon Apr 26 '12 at 7:54
Also, it is funny that you write big o, instead of big O. O and o are different! –  Aryabhata Apr 26 '12 at 17:12

$g(x) \in O(f(x))$ means that $\exists c, x_0: \forall x \gt x_0: g(x) < c \cdot f(x)$. So any function works if it grows at least as fast as $g(x)$ up to a constant multiple. For example, all of $g(x) \in O(g(x))$, $g(x) \in O(\frac{1}{17} \cdot g(x))$, $g(x) \in O(x^{x+4})$, $g(x) \in O(x^{x^x})$ are true.

-
Because $g(x) \le x! \cdot x^4$ and $x! \le x^x$, so $g(x) \le x^x \cdot x^4 = x^{x+4}$. –  Dan Brumleve Apr 26 '12 at 8:12
(Note that $\forall x: g(x) \le f(x)$ implies $g(x) \in O(f(x))$.) –  Dan Brumleve Apr 26 '12 at 8:18

Stirling's approximation gives you

$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n.$

This implies $n! \in \Theta(\sqrt{n}\cdot n^n\cdot e^{-n}$) which in turn implies for example

$\qquad \displaystyle n! \in o(n^n) \subseteq O(n^n).$

-