Why is $3^n = 2^{O(n)}$ true?

Problem Detail: 

$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2.

How is $3^n = 2^{O(n)}$ true?

Asked By : David Faux

Answered By : SamM

With some algebra (and changing the constant in the $O(n)$), we can actually change the bases.

$$3^n = (2^{\log_2 3})^n = 2^{n\log_2 3}$$

Since $\log_2 3$ is a constant, $n\log_2 3 = O(n)$. So $3^n = 2^{O(n)}$.

I'm not sure what you mean by "$3^n$ grows faster than any exponential function with a base of 2." $2^n = o(3^n)$ of course but it seems you mean something more general. My guess is that your statement applies to something like $O(3^n)$, where you multiply the base by a constant, as opposed to $2^{O(n)}$ where you multiply the number in the exponent by a constant.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7091