2
$\begingroup$

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!

  • 0
    Also, it is funny that you write big o, instead of big O. O and o are different!2012-04-26

2 Answers 2

2

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

  • 0
    (Note that $\forall x: g(x) \le f(x)$ implies $g(x) \in O(f(x))$.)2012-04-26
1

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).$