# Is this big O notation format correct? $3^n = 2^{(O(n))}$

I am completing a university exercise deciding whether big notations are true or false.

I am stuck on this question :

$$3^n = 2^{(O(n))}$$

I want to answer False as the format looks incorrect and I have never seen big O notation written is this way.

Is this a valid way to write big O notation?

Sure, that is a correct notation. It is also a correct statement. Essentially it is a compact way to say the following:

$$\exists c>0, \exists n_0 \ge 0 : \forall n>n_0, 3^n \le 2^{c n}$$.

You can pick any $$c \ge \log_2 3$$ and $$n_0 = 0$$.

Yes, this is a valid way to write big O notation, or at least it is used in multiple research papers that I have read. The notation $$f(n) = 2^{O(n)}$$ means that there exists a constant $$c$$ such that $$f(n) = O(2^{cn})$$, or further simplified that there exists a constant $$c$$ such that $$f(n) = O(c^n)$$.

I'd take it as a shortcut meaning: There is a function f(n) such that $$3^n = 2^{f(n)}$$, and f(n) = O (n).

Since big-O notation is just a handy shortcut for a rather long statement anyway, your statement is slightly pushing the boundaries, but I'd say it is correct.

Big-oh notations can be added, multiplied, and even exponentiated. But this is very confusing, what does it mean? The best way to think of it is as gnasher729 says: whenever you see $$O(n)$$ in an expression, you can replace that with some function $$f(n)$$ which is $$O(n)$$.

For example, $$O(n) \cdot O(n)$$ means $$f(n) \cdot g(n)$$, where $$f$$ and $$g$$ are some unknown functions and $$f \in O(n)$$ and $$g \in O(n)$$. Similarly, $$2^{O(n)}$$ means $$2^{f(n)}$$ where $$f$$ is some unknown function such that $$f \in O(n)$$, that is $$f(n) \le C n$$ for some constant $$C$$. And for a more complex example, you can write something like $$O(n^2) - O(n) = O(n^2)$$ What this true statement means is that, given some unknown functions $$f$$ and $$g$$ such that $$f(n) \in O(n^2)$$ and $$g(n) \in O(n)$$, $$f(n) - g(n)$$ is in $$O(n^2)$$, that is, $$f(n) - g(n) \le C n^2$$.