Prove that $3^n$ is not $O(2^n)$.

Question

I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have:

Prove that $3^n$ is not $O(2^n)$

I can see that its obvious just by looking at the two functions, but I don't know how to prove it. What are the steps one should take to approach to disprove something like this?

Thanks

Answer 1

$a(n)=O(b(n))$ means that there is a bounded function $f$ such that $a(n)=f(n)b(n)$. So if you prove that $\displaystyle{\frac{3^n}{2^n}}$, you are done.

Now,

$$\frac{3^n}{2^n}=\left(\frac{3}{2}\right)^n$$

And $\frac32=1.5>1$. Can you conclude? It may be more obvious if you notice that

$$\left(\frac{3}{2}\right)^{2n}=\left(\frac{9}{4}\right)^{n}>2^n$$

Answer 2

What you want to argue is that there does not exist an $M$ such that $3^n \le M 2^n$ for all $n$ sufficiently large. Suppose such an $M$ existed. Then you would have that $\left(\dfrac{3}{2}\right)^n \le M$. Can you see how to proceed?

Answer 3

Assume that $3^n \in O(2^n)$. Then exists constant $C \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, that:

$$\forall n>n_0 \; 3^n \leq 2^nC$$

But it's equal:

$$\forall n>n_0 \; (\frac{3}{2})^n \leq C$$

It isn't true, because $\lim_{n \to \infty}(\frac{3}{2})^n=\infty$.

Answer 4

You want to show that for every c, there exists $k$ such that $3^{n} > 2^{n}c$ when $n > k$.

Let $c$ be fixed, then as long as $\frac{3}{2}^n > c$ i.e. $n >= k > \frac{\ln{c}}{\ln(\frac{3}{2})}$. Since this exists for all $c>0$ we have that $3^{n}$ is not the same order as $2^{n}$.