2
$\begingroup$

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?

  • 1
    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.2012-10-18

2 Answers 2

1

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.

1

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.