8
$\begingroup$

Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$.

It feels natural to write that the running time on this graph would be $O(O(V^2)+V)$ and then simplify to $O(V^2)$.

Are there any pitfalls to using such a "remove-the-nested-O" shortcut (not just in this case, but more generally)?

$\endgroup$
  • 4
    $\begingroup$ If you work through the definition of big-O, you'll see that nested Os are both natural and redundant, and that the rule of dropping the inner O is correct. $\endgroup$ – Dave Clarke Oct 7 '12 at 9:09
  • $\begingroup$ As V is in O(V^2) I guess you could replace O(V^2) with V if you did not know what you were doing? $\endgroup$ – The Unfun Cat Oct 7 '12 at 9:26
  • 3
    $\begingroup$ If you don't know what you are doing, you can do arbitrarily wrong things. $\endgroup$ – Dave Clarke Oct 7 '12 at 9:53
  • 4
    $\begingroup$ Indeed. = is not = in big-O land. $\endgroup$ – Dave Clarke Oct 7 '12 at 11:12
  • 3
    $\begingroup$ See also this excellent question on math.SE about = in Landau notation. $\endgroup$ – Raphael Oct 7 '12 at 13:02
14
$\begingroup$

Let me start of with a recommendation: treat Landau notation just as you (should) treat rounding: round rarely, round late. If you know something more precise than $O(.)$, use it until you are done with all calculations, and Landauify at the end.


As for the question, let's dig through this abuse of notation¹. How would we interpret something like $h \in O(f + O(g))$? We should replace $O$ with its definition from the inside out. So, we get

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

and then

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

which is equivalent to

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

As certainly² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, we see that this is equivalent to $h \in O(f + g)$; the loss of precision is ignored by $O$ anyway.


What about other combinations, say $h \in O(f + \Omega(g))$? If we try the same here, we get

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

But this is a tautology: $h$ is certainly bounded above by something arbitrarily large. So, combining upper and lower bounds in this fashion is not meaningful.


  1. $O(.)$ and the other Landau symbols map functions to function classes. Feeding it a function class is not immediately meaningful.
  2. At least if we consider only positive functions, which we can safely assume when talking about runtimes. I'm not sure this works in general.
$\endgroup$
2
$\begingroup$

I just wanted to add this because I recently encountered it. While this shortcut is fine with addition and multiplication (when not mixing $O$ with $\Omega$; see the accepted answer), care must be taken when using exponents. For instance: $$O(n^{O(m)}) \not= O(n^m).$$ In this example, $n^{2m}$ belongs to the first class but not to the second.

$\endgroup$
1
$\begingroup$

By definition, $O(g)$ is a set and if you use this notation nested, you would have a set in a set, which would be wrong.

The definition of the O-Notation

$O(g) = \left \lbrace f|\exists c > 0\exists x_0>0 \forall x > x_0: |f(x)| \leq c *|g(x)|\right \rbrace $

The mistake

You used terms like $ O(O(n)+k)$ where k and n are functions and $O(n)$ is a set. But what is the result of a function added to a set? It is not defined!

Correct version

Instead of using the Landau-Symbols nested, you can do the following: $O(m+k),m \in O(n)$

$\endgroup$
  • 2
    $\begingroup$ Yes, but Landau notation is frequently abused for the sake of (alleged) ease of use, so we better make sure everybody understands the same thing. See here for a structured approach. $\endgroup$ – Raphael Oct 9 '12 at 22:21
0
$\begingroup$

In Section 9.3 "$O$ Manipulation" of the book Concrete Mathematics (Second Edition), Knuth has listed some rules of manipulation on the $O$-notation (In the following, I assume that both $f(n)$ and $g(n)$ are positive; notice that the ordering of rules has been changed).

\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}

By (3), you can wrap/unwrap a function $f(n)$ with an O-notation. Then by (5), you can actually wrap/unwrap (or called, nest) it arbitrarily finite times. Using (4), you can also add/remove constant multiplication factors to/from $O$.

Then, (2) and (6) allow you to manipulate nested $O$-notations in the way compatible with $+$ and $\times$.

$\endgroup$

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.