# Is it true that $2^{O(3k)} = 2^{O(k)}$?

Is it true that $$2^{O(3k)} = 2^{O(k)}$$?

But It should be different from $$O(2^{k}) = 2^{O(k)}$$ ?

I will be happy for simple explanation.

Thanks.

• Because $O(3k) = O(k)$. Are you happy? Apr 24, 2021 at 16:36
• But It should be different from $O(2^{k})= 2^{O(k)}$ ? Apr 24, 2021 at 16:42
• $2^{2k}$ belongs to $2^{O(k)}$ but not $O(2^{k})$. Apr 24, 2021 at 16:50

$$\mathcal{O} (3k) = \mathcal{O} (k)$$ because $$\mathcal{O} (k)$$ can be defined like this:

$$\tag{1} d = \mathcal{O} (k) \implies d \le Ck ,$$ for some constant $$C>0$$ and for all $$k$$ larger than some threshold, and similarly $$\mathcal{O}(3k)$$ would be defined as:

$$\tag{2} d_3 = \mathcal{O}(3k) \implies d_3 \le C_3 (3 k),$$

for $$C_3 > 0$$ and for all $$k$$ larger than some threshold.

Now remember that $$C$$ and $$C_3$$ are positive, so $$3C_3 > C$$, which means that if $$d_3 = \mathcal{O}(3k)$$ then it must also be $$\mathcal{O}(k)$$.

Then since $$2^k$$ is a monotonic function, we also have that $$2^{\mathcal{O}(3k)} = 2^{\mathcal{O}(k)}$$.

Some will argue that specifying the extra constant of "3" is redundant and formally improper, but you might still find that constant explicitly written in some papers, especially by people that don't know the above definition and tend to use big-O notation with (some would say regrettable) looseness.

## The bottom line: If you know the constant hiding under the Big-O is 3, you might as well just say $$d \le 3k$$ instead of $$d=\mathcal{O}(3k)$$.

$$2^{\mathcal{O}(k)}$$ gives us everything of the form $$2^l$$ where $$l \le Ck$$ under the conditions of Eq. 1.
By monotonicity of the function $$2^l$$ we have everything smaller than $$2^{Ck} = (2^C)^k$$ under similar conditions.

Let's consider the example where $$C=2$$.

• Your question becomes whether or not $$\mathcal{O}(2^k) = \mathcal{O}(4^k)$$, but since there is no constant $$C$$ such that $$4^n \le C 2^n$$, it is not true that $$\mathcal{O}(2^k) = \mathcal{O}(4^k)$$.
• Therefore it is also not true that $$\mathcal{O}(2^k) = \mathcal{O}(2^{Ck})$$ and:
• it's also not true that $$\mathcal{O}(2^k) = 2^{\mathcal{O}(k)}$$.

## Conclusion: $$\mathcal{O}(2^k) \ne 2^{\mathcal{O}(k)}$$ in general.

• But It should be different from $O(2^{k})= 2^{O(k)}$ ? Apr 24, 2021 at 16:43

Yes:

$$O(3k) = O(k)$$, and thus $$2^{O(3k)}=2^{O(k)}$$.

For a rigorous proof, try using the definition of big-O and the monotonicity of the function $$f(x)=2^x$$.

### Rigorous proof of the fact

(The statement the OP asked immediately follows because of the equality of the sets $$O(3k)$$ and $$O(k)$$) We will prove a stronger statement.

Theorem: If $$h(n)=O(g(n))$$, and $$f$$ is a monotonically increasing function, then $$f(h(n)) \in f(O(g(n)))$$.

Proof: since $$h(n)=O(g(n))$$, then there is some $$c>0$$ and $$n_0\in \mathbb{N}$$ such that for all $$n>n_0$$, $$h(n)\le cg(n)$$. Since $$f$$ is monotonically increasing, then $$f(h(n))\le f(cg(n)) \in f(O(g(n)))$$. Thus $$f(h(n)) \in f(O(g(n)))$$.

• But It should be different from $O(2^{k})= 2^{O(k)}$ ? Apr 24, 2021 at 16:43
• As I said, for a rigorous proof, you need to use the fact that $2^x$ is a monotonically increasing function. I will edit the post and add the formal proof in a minute or so Apr 24, 2021 at 16:45
• Also, @John19 $O(2^k)$ is different from $2^{O(k)}$. The first is everything bounded by $c2^k$, and the latter is everything bounded by $2^{ck}=(2^k)^c$ for any arbitrary constant $c$. Apr 24, 2021 at 16:55
1. For $$C \gt 0$$ we have $$C\cdot O(g)=O(C\cdot g) = O(g)$$.

2. Taking non negative case, if $$f(n) \in O(2^n)$$, then, in appropriate conditions, $$f(n)\leqslant C 2^n= 2^{n+\log_2 C} \leqslant 2^{2n} \in 2^{O(n)}$$.

On other hand $$2^{2n} \notin O(2^n)$$. So, we have only $$O(2^n) \subset 2^{O(n)}$$.