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^{nlog_2 3}$$ Since $log_2 3$ is a constant, $nlog_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
