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?
Best Answer
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.