Is it true that $3^n = 2^{O(n)}$?

Question

I know that the two main rules are dropping low order terms and dropping constant factors.

For example:

$50n = O(n)$

$5n^2 + 3n + 45 = O(n^2)$

But in a textbook I found the question:

Is it true that $3^n = 2^{O(n)}$?

The answer is true but I do not understand why it is not $3^{O(n)}$. I know you cannot just drop the base completely but why is $3$ changed to $2$?

Answer 1

Let's try to solve $3^n = 2^m$ for $m$.
First, use a log on both sides: $$n \log(3) = m \log(2).$$

Now, solve for $m$: $$m = \frac{\log(3)}{\log(2)} n.$$

Obviously, we now have $m = O(n)$, they only differ by a constant. Therefore, we can say $$3^n = 2^{O(n)}.$$

So yes, in some sense you can drop the base, we always have $$a^n = b^{O(n)}$$ as long as $a,b > 1$.

Note that it wasn't claimed that $$3^n = O(2^n),$$ as this would be wrong.

Answer 2

$\large\displaystyle 3^n = 2^{n \cdot \log_23}$

Notice that $\log_23$ is a constant, so it can be written as $2^{O(n)}$.

Yes, it could be written as $3^{\text{O}(n)}$, but the question was just asking if it's true.