Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
Beware the abuse of notation! –  Raphael Dec 3 '12 at 8:11
    
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. –  user742 Dec 3 '12 at 8:40
    
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. –  David Richerby Sep 19 '13 at 17:28
add comment

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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