Nested Big O-notation

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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)$

Answer 4

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$.