2
$\begingroup$

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?

$\endgroup$

4 Answers 4

4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.