# Big - O estimation

I want to establish a Big-O estimate for the following:

$$(n! + 2^{n+3})(111n^3 + 15\log(n^{201} +1))$$

Would the following be correct?

• $n! = O(n^{n})$

• $2^{n+3}=O(2^{n+3})$

• $111n^{3}=O(n^{3})$

• $15\log(n^{201} +1)= O(15\log n^{201})$

Therefore the dominant term appears to derive from $(n!)\cdot(111n^{3})$ which would give us $O(n^{n+3})$. Would this be correct?

-
It's OK. Can do somewhat better, because of the $e^{-n}$ term in the Stirling approximation to the factorial, but $O(n^{n+3})$ is certainly true. – André Nicolas Oct 18 '12 at 18:46
Thanks Andre and Ganesh – bosra Oct 18 '12 at 18:56

Yes, this is right. For a correct Big $O$ estimate, expand out , find the dominant term and then simplify; don't take big $O$ estimates in intermediate steps. In your expression,the dominant term is $111n! n^3$ as you say which is $O(n^{3+n})$. You could even say your expression is $O(n!n^3)$ which is somewhat simpler and tighter.

If you are comfortable with more advanced maths, then you can use

$$n! \approx \sqrt{2\pi n} (\frac{n}{e})^n = O(\frac{n^{n+1/2}}{e^n})$$

leading to a dominant term $n!n^3 =O( \frac{n^{n+7/2}}{e^n})$ after simplifying.

-

Your dominating term is indeed $n!n^3$. However I would write the bound differently. In particular, $$n!n^3< n^n n^3=2^{\log n ^{n}} n^3= 2^{n \log n } n^3 =O(n^3 2^{n\log n}).$$

By slightly abusing the big-O notation it is often common to write $2^{O(n\log n)}$ instead of the last expression.

-