patternModerate
Why is $3^n = 2^{O(n)}$ true?
Viewed 0 times
whytruestackoverflow
Problem
$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?
How is $3^n = 2^{O(n)}$ true?
Solution
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.
$$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.
Context
StackExchange Computer Science Q#7091, answer score: 12
Revisions (0)
No revisions yet.