What are you allowed to move into the big O notation for it to be still correct?

Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct?

For example: Is this $\log(O(n))= O(\log(n))$ correct? Or is this correct $O(n)^2=O(n^2)$? Or am I not allowed to do this?

To prove or disprove this kind of equality with $\mathcal{O}$, you need to go back to the definition of $\mathcal{O}$ with inequalities.

For example, let's study the question $\log(\mathcal{O}(n)) = \mathcal{O}(\log n)$:

$f\in \log(\mathcal{O}(n))$ means that there exists a function $g\in\mathcal{O}(n)$ so that $f = \log g$. That means there exists a constant $A>0$ such that:

$$f(n) = \log g(n) \leqslant \log (An) = \log A + \log n\leqslant 2\log n$$

The first inequality holds true because $\log$ is an increasing function. The second inequality holds true for $n$ big enough. We proved that $f \in \mathcal{O}(\log n)$.

Reciprocally, $f\in \mathcal{O}(\log n)$ means that there exists $B>0$ such that $f(n) \leqslant B\log n$. That means:
$$2^{f(n)}\leqslant 2^{B\log n} = n^B$$
Therefore, we cannot conclude that $2^f\in \mathcal{O}(n)$, or equivalently that $f\in \log(\mathcal{O}(n))$.

For example, consider $f(n) = 2\log n$. Then clearly, $f\in \mathcal{O}(\log n)$, but $2^{f(n)} = n^2 \notin \mathcal{O}(n)$.

In the general case, we have:

• $\log(\mathcal{O}(n))\subsetneq \mathcal{O}(\log n)$;

• $(\mathcal{O}(n))^k = \mathcal{O}(n^k)$;

• $\mathcal{O}(2^n) \subsetneq 2^{\mathcal{O}(n)}$.

StackExchange Computer Science Q#145977, answer score: 15