7
$\begingroup$

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?

$\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$ Nov 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$
    – user21820
    Nov 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$ Nov 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$
    – user21820
    Nov 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$ Nov 23, 2021 at 4:08

3 Answers 3

15
$\begingroup$

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)}$.
$\endgroup$
5
  • $\begingroup$ But is log(O(n^k))=O(log(n)) ok? $\endgroup$
    – OttoFran
    Nov 21, 2021 at 14:41
  • 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$
    – Nathaniel
    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$
    – Nathaniel
    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$
    – Nathaniel
    Nov 22, 2021 at 17:27
8
$\begingroup$

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.

$\endgroup$
2
  • 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$
    – Nathaniel
    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$
    – Steven
    Nov 21, 2021 at 14:21
2
$\begingroup$

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.

$\endgroup$
2
  • 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$
    – Steven
    Nov 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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