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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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