Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
