Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
$\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&gt;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 &gt; 0$ and for all $k$ larger than some threshold.
Now remember that $C$ and $C_3$ are positive, so $3C_3 &gt; 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 &quot;3&quot; 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.