Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
There is no "the" which will fill the $???$ in $O(???)$. –  Aryabhata Apr 26 '12 at 7:52
1  
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.