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

Question

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.

Answer 1

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

---

You've added a new question to your post after two of us already answered the first one. For the second question:

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

Answer 2

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

Answer 3

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