Proving Big Oh with Hierarchy Theorem

Question

I need help with proving that

$$ 100n^2+(0.5)^{15^{15^{15}}} \cdot 2^n = O(2^n).$$

I started by using the definition:

There should exist $c$ and $n_{0}$ in the positive reals such that, for all $n$ in the naturals,

$$n\geq n_{0} \implies 100n^2+(0.5)^{15^{15^{15}}} \cdot 2^n \leq c 2^n.$$

Now,

$n_{0}=?$

$c=?$

Let $n$ be in the naturals and assume $n \geq n_{0}$.

How do you complete this? Maybe start with $2^n$ in big oh $2^n$ by big Oh theorems?

Answer 1

Observe that for $n \geq 15$, $$ 100n^2 \leq 2^n $$ and for $n \geq 1$, $$ \left(\frac{1}{2}\right)^{15^{15^{15}}}\cdot2^n \leq 2^n $$ because $\left(\frac{1}{2}\right)^{15^{15^{15}}} < 1$. Therefore, for $n \geq 15$, we have $$ 100n^2 + \left(\frac{1}{2}\right)^{15^{15^{15}}}\cdot 2^n \leq 2 \cdot 2^n $$ That is, you can set $n_0$ as $15$ and $c$ as $2$ to prove the bound.

---

In general, you do not need to find the exact values of $n_0$ and $c$. You only need to decide which term is the most dominant term. For example, in your question, we have $$ 100n^2 = \mathcal{O}(n^2) \quad\text{ and }\quad \left(\frac{1}{2}\right)^{15^{15^{15}}}\cdot 2^n = \mathcal{O}(2^n) $$ $\mathcal{O}(2^n)$ is the dominant term, comparing with $\mathcal{O}(n^2)$. Therefore, $$ 100n^2 + \left(\frac{1}{2}\right)^{15^{15^{15}}}\cdot 2^n = \mathcal{O}(2^n) $$

Answer 2

Note that you do not really need to find an explicit $n_0$

In fact you have $100n^2+c\; 2^n$ with $c=(.5)^{15^{15^{15}}}$ and $100n^2$ is negligible before $2^n$ so the whole thing is an $O(2^n)$.

Now if you really want an $n_0$ then consider $f(x)=2^x-100x^2$

$g(x)=\ln(f(x))=x\ln(2)-2\ln(x)-\ln(100)$ and $g'(x)=\ln(2)-\frac 2x$ which is positive for $x\ge 3$.

So $f$ is increasing for $x\ge 3$, yet since $f(15)=10268 > 0$ then for $n\ge n_0=15$ we have $|100n^2+(.5)^{15^{15^{15}}}2^n| < (c+1)2^n$ and we are done.