$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?

  • 1
    $\begingroup$ Beware the abuse of notation! $\endgroup$
    – Raphael
    Dec 3, 2012 at 8:11
  • $\begingroup$ Really I can't understand what does $3^n = 2^{O(n)}$ mean? first I changed it to $3^n \in 2^{O(n)}$, after that I saw again this is meaningless. IMO question is meaningless. $\endgroup$
    – user742
    Dec 3, 2012 at 8:40
  • 1
    $\begingroup$ It's extremely common to write $f(x)=O(g(x))$ for what should in the strictest sense be $f(x)\in O(g(x))$. So common that it's hardly even considered an abuse of notation. $\endgroup$ Sep 19, 2013 at 17:28

3 Answers 3


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$ grows faster than any exponential function with a base of $2$.

True. This implies that $3^n = O(2^n)$ cannot be true. But what you have here is $2^{O(n)}$.

Recall that $O(f(n))$ is really a set of functions, and strictly speaking we should be writing $3^n \in 2^{O(n)}$ (or even $(n \mapsto 3^n) \in 2^{O(n \mapsto n)}$). The right-hand side is not the exponential of a function, but the exponential of a set of functions. Expanding the definition of big oh:

$$ 2^{O(n)} = 2^{\{f \;\mid\; \exists N, \exists p, \forall n \ge N, f(n) \le p n\}} = \{(n \mapsto 2^{f(n)}) \mid \exists N, \exists p, \forall n \ge N, f(n) \le p n\} $$

Since the exponential function $n \mapsto 2^n$ is increasing, we can lift the inequality out of the exponential:

$$ 2^{O(n)} = \{g \mid \exists N, \exists p, \forall n \ge N, g(n) \le 2^{p \, n}\} $$

Contrast with $$ O(2^n) = \{g \mid \exists N, \exists k, \forall n \ge N, g(n) \le k \, 2^{n}\} $$

In $2^{O(n)}$, the multiplicative constant is inside the exponential. In $O(2^n)$, it is multiplied by the exponential. $2^{p \, n} = 2^p 2^n$, so we have (for any $n \ge 0$) $3^n \le 2^{\log_2 3} 2^n$, i.e. we can take $N = 0$ and $p = \log_2 3$, showing that $3^n \in 2^{O(n)}$.


$3^n=2^{O(n)}$ is in fact true because if you recall $O(n)$ definition you will see that you can add/multiply by any constant. So:

$3^n < 2^{kn}$ // $ \log_2 $

$n\log_2(3^n) < kn\log_2(2)$

$k > \log_2(3) $

So as you can see $2^{kn}$ is bigger then $3^n \iff k > \log_2(3)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.