# Why is $3^n = 2^{O(n)}$ true?

$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
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. – Saeed Amiri Dec 3 '12 at 8:40

## 3 Answers

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 38, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9486110210418701, "perplexity_flag": "head"}