# Proving big oh by notation with full expression power

I am trying to prove that:

$(n^2 + 1)^{10}$ is $O(n^{20})$

but I am not able to figure out how can I prove it with full expression having a power. Any suggestions?

We have that

$$(n^2+1)^{10}\le (2n^2)^{10}=2^{10}n^{20}.$$ That is,

$$(n^2+1)^{10}\le 2^{10}n^{20}.$$ Thus

$$(n^2+1)^{10}=O(n^{20}).$$

• What made you choose $(2n^2)^{10}$? – user6607 Mar 19 '15 at 22:21
• @user6607 $(n^2 + 1)^{10} \leq (n^2 + n^2)^{10} = (2n^2)^{10}$ if $n \geq 1$. – G. Bach Mar 19 '15 at 22:52

We have:$$\dfrac{\left(n^2+1\right)^{10}}{n^{20}} = \left(\dfrac{n^2+1}{n^2}\right)^{10} \leq 2^{10} = C$$

Simply with equivalents and asymptotic analysis:

$n^2 + 1\sim_\infty n^2$, hence $(n^2 + 1)^{10}\sim_\infty n^{20}$, hence $(n^2 + 1)^{10}=\substack{\textstyle O\\n\to\infty}\bigl(n^{20}\bigr)$.