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?
$\begingroup$
$\endgroup$
11
-
8$\begingroup$ 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. $\endgroup$– paul garrettNov 21, 2021 at 23:19
-
1$\begingroup$ @paulgarrett: It is not symmetric even if you treat it as a set....... $O(n^2) ≠ O(n)$. $\endgroup$– user21820Nov 22, 2021 at 15:33
-
2$\begingroup$ @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. $\endgroup$– paul garrettNov 22, 2021 at 17:08
-
1$\begingroup$ @paulgarrett: Absolutely, that's why I use "⊆" where appropriate, and never "=" if it is not truly equal. $\endgroup$– user21820Nov 22, 2021 at 17:31
-
1$\begingroup$ 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? $\endgroup$– Owen ReynoldsNov 23, 2021 at 4:08
|
Show 6 more comments
3 Answers
$\begingroup$
$\endgroup$
5
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)}$.
answered Nov 21, 2021 at 14:11
-
-
2$\begingroup$ 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))$. $\endgroup$ Nov 21, 2021 at 14:44
-
2$\begingroup$ However, I think $\bigcup\limits_{k\geqslant 0}\log(\mathcal{O}(n^k)) = \mathcal{O}(\log n)$. $\endgroup$ Nov 21, 2021 at 14:45
-
$\begingroup$ $g(n)=e^{-n}$ is $\mathcal O(n)$, but $\log g(n)=-n$ is not $\mathcal O(\log n)$ $\endgroup$ Nov 22, 2021 at 15:17
-
$\begingroup$ @HagenvonEitzen That's right, I was implicitly considering positive functions. $\endgroup$ Nov 22, 2021 at 17:27
$\begingroup$
$\endgroup$
2
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.
-
3$\begingroup$ 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)$. $\endgroup$ Nov 21, 2021 at 14:19
-
1$\begingroup$ @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! $\endgroup$– StevenNov 21, 2021 at 14:21
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ 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)) \}$. $\endgroup$– StevenNov 23, 2021 at 10:38
-
$\begingroup$ @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. $\endgroup$ Nov 26, 2021 at 3:09