8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Beware the abuse of notation! $\endgroup$ – Raphael Dec 3 '12 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 '12 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$ – David Richerby Sep 19 '13 at 17:28
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

$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)}$.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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