I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$.
To prove $3^n \in O(2^n)$, we must find $n_0$, $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.
$$
\begin{aligned}
3^n &\leq c \cdot 2^n\\
\left(\frac{3}{2}\right)^n& \leq c
\end{aligned}
$$
I am stuck here….
I could use a log here, but I don't see the use
Any hint?
UPDATE
$$
\begin{aligned}
3^n &\geq c \cdot 2^n\\
\left(\frac{3}{2}\right)^n& \geq c\\
n \log(3/2) &\geq \frac{\log c}{\log 3/2}\\
n &\geq \log \frac{2c}{3}
\end{aligned}
$$
For every $n \geq \log \frac{2c}{3}$, $3^n \geq 2^n$. Therefore, $3^n$ is not $O(2^n)$.
Best Answer
Your goal is to prove that no value of $c$ can work.
One way of doing so is to show that the equation $(3/2)^n \geq c$ has infinitely many solutions for $n$. Do you see why that is?