# 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?

• Also, as you may already realize, being in Computer Science, "equality" is not symmetrical, especially with regard to big-O notation, as in $f(x)=O(g(x))$, because it's really/more precisely $f(x)\in O(g(x))$... So some versions of this question (and of answers) can be inadvertently garbled by at some moments accidentally treating equality with regard to big-O stuff as if it were symmetric. It can be, if we realize that $O(f(x))$ is a set, not a single thing, etc. Nov 21 '21 at 23:19
• @paulgarrett: It is not symmetric even if you treat it as a set....... $O(n^2) ≠ O(n)$. Nov 22 '21 at 15:33
• @user21820, right, sets can be equal, but also only contained, etc., so to write $O(n)\subseteq O(n^2)$ makes sense and is correct. Nov 22 '21 at 17:08
• @paulgarrett: Absolutely, that's why I use "⊆" where appropriate, and never "=" if it is not truly equal. Nov 22 '21 at 17:31
• Just curious, did log(O(n)) come up in a real problem? If so, how? I'm trying to imagine a function that runs in O(n), then you're somehow taking the log of ... that function? Is log(O(n)) even well-defined? Nov 23 '21 at 4:08

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)}$$.
• But is log(O(n^k))=O(log(n)) ok? Nov 21 '21 at 14:41
• No, because if $f(n) = (k+1)\log n$, then $f\in \mathcal{O}(\log n)$, but $2^{f(n)} = n^{k+1}$, so $f\notin \log(\mathcal{O}(n^k))$. Nov 21 '21 at 14:44
• However, I think $\bigcup\limits_{k\geqslant 0}\log(\mathcal{O}(n^k)) = \mathcal{O}(\log n)$. Nov 21 '21 at 14:45
• $g(n)=e^{-n}$ is $\mathcal O(n)$, but $\log g(n)=-n$ is not $\mathcal O(\log n)$ Nov 22 '21 at 15:17
• @HagenvonEitzen That's right, I was implicitly considering positive functions. Nov 22 '21 at 17:27

In order for $$f(O(n)) \in O(f(n))$$ to hold you essentially want $$f$$ to satisfy $$f(cn) \le df(n)$$ where $$n$$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $$c$$, while $$d$$ is a constant that can be chosen as a function of $$c$$ (but not as a function of $$n$$).

For example $$\log cn \le \log c + \log n \le (1+ \log c) \log n$$ for $$n \ge 2$$ and $$c \ge 1$$, so you can pick $$d=(1+ \log c)$$.

Also: $$(cn)^2 = c^2 n^2$$ for any $$c \ge 0$$ so you can pick $$d=c^2$$.

Notice that you can't just move any function into the Big-Oh notation. For example $$2^{O(n)} \not\in O(2^n)$$. Indeed, when $$c > 1$$, you can always satisfy $$2^{cn} > d 2^n$$ for any $$d$$ chosen independently of $$n$$, by simply considering values of $$n$$ that are large enough.

• I think that $2^{O(n)}$ is not equal to $O(2^n)$. For example, $2^{2n}$ is clearly in $2^{O(n)}$, but since it is equal to $4^n$, it is not in $O(2^n)$. Nov 21 '21 at 14:19
• @Nathaniel. Yep, you are right. That's exactly what that sentence was trying to point out but I realize that it was really confusing. I rephrased the last paragraph, it should read better now. Thanks! Nov 21 '21 at 14:21

Although $$\mathcal O(f(n))$$ will often be given as a function, e.g. $$\mathcal n^2+n=\mathcal O(n^2)$$, strictly speaking $$\mathcal O(f(n))$$ is a set of functions, so the precise statement is $$n^2+n \in \mathcal O(n^2)$$. The expressions $$\mathcal \log(O(f(n))$$ and $$\mathcal O(f(n))^2$$ don't really make sense. You can't do math on $$\mathcal O(f(n))$$, other than set operations.

• What you say is formally correct but writing, e.g., $f(n) = 2^{O(n)}$ is a commonly accepted abuse of notation to mean that there exists some function $g(n) \in O(n)$ such that $f(n) = 2^{g(n)}$. Then $\log O(f(n))$ would be the set $\{ \log g(n) \mid g(n) \in O(f(n)) \}$ and $O(f(n))^2$ would be the set $\{ (g(n))^2 \mid g(n) \in O(f(n)) \}$. Nov 23 '21 at 10:38
• @Steven If I were to see $O(f(n))^2$ I would immediately think $O(f(n))\times O(f(n))$, putting it next to other abuses of notation helps imply the intended meaning, but I definitely don't think it's a good idea for the sake of the reader to extend this abuse of notation arbitrarily. Nov 26 '21 at 3:09