Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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).$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.