The Exponent Is the Terrain

At first glance, $3^{n^3+4n+2}$ seems larger because its base is $3$. The calmer way to compare it is to put both expressions over the same base:

$$3^{n^3+4n+2}=2^{({\log }_{2}3)(n^3+4n+2)}=2^{\Theta (n^3)}.$$

The factor ${\log }_{2}3$ changes the scale of the exponent, but not its polynomial degree. The expression still lives on a cubic exponent.

When the constants move

Now compare $2^{O(n^3)}$ with $O(2^{n^3})$ using Big-O notation. Both mention the same cubic scale, but the $O$ sits in a different place:

$$\begin{array}{rlrl}{2}^{O(n^3)}& ⇝2^{c{n}^3}& & \text{constant inside the exponent},\\ O(2^{n^3})& ⇝C\cdot 2^{n^3}& & \text{constant outside the exponent}.\end{array}$$

Here $c,C>0$. The first notation allows the exponent itself to be rescaled; the second only multiplies the finished exponential.

Take $2^{2n^3}$. It satisfies

$$2^{2n^3}\in 2^{O(n^3)},$$

but

$$\frac{2^{2n^3}}{2^{n^3}}=2^{n^3}⟶\infty ,$$

so $2^{2n^3}\notin O(2^{n^3})$. See the limit-form definition of Big-O notation.

Here is the same separation as a picture. Literal exponentials become enormous quickly, so the vertical axis shows ${\log }_{2}T(n)$. Take $4\cdot 2^{n^3}$ as a representative of the outside-$O$ form and $2^{2n^3}$ as a representative of the inside-$O$ form.

The two notations are therefore not interchangeable. First normalise the base and inspect the exponent; then check where $O$ lives. The exponent tells you which terrain you are walking through, while the position of $O$ tells you how wide the path may be.