[Solved]: Nested Big O-notation

Problem Detail: 

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

Asked By : The Unfun Cat

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4913