If I have a graph algorithm that has a linear part of $O(|E|+|V|)$, and one more part of $O(|V|^2)$, is it still $O(|E|+|V|)$?
Date: 24 Apr 2015 12:25
Number of posts: 3
RSS: New posts
When in doubt, go back to the formal definitions of big O notation…
$O(|V|+|E|)$ means that there is a constant such that for any values of $|E|, |V|$….(make sure you can fill this in)… This means that it has to hold for ANY graph.
As a very simple example, which algorithm would you prefer for running on a tree, one whose running time is $O(|V^2|)$ or $O(|V|+|E|)$?