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.
- $O(.)$ and the other Landau symbols map functions to function classes. Feeding it a function class is not immediately meaningful.
- 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
