Question Big-Oh Graph Algorithm

Question

A question regarding the big-Oh notation in Graph Theory. Some graph algorithms, like topological sort can be executed in $\mathcal{O}(|V| + |E|)$ steps, where $|V|$ and $|E|$ are the number of nodes and edges respectively. However, since $|V| < |E|$, doesn't this imply that the algorithm runs in $\mathcal{O}(|E|)$? What am i missing here?

Answer 1

Indeed, as the comments state, $|V| < |E|$ is not necessarily the case. To illustrate an extreme example, consider the null graph (no edges) on $|V|$ vertices. Then, the runtime becomes $O(|V| + |E|) = O(|V| + 0) = O(|V|)$, which is certainly not $O(|E|)$ as $|E| = 0$ is constant. In general, you need to keep the $|V|$ term around should the situation of $|V| > |E|$ arise. Thus, to gracefully handle all the cases (whether $|V| < |E|$ or $|V| > |E|$ or $|V| = |E|$), it is concise to leave the runtime as $O(|V| + |E|)$.

Perhaps you are thinking about connected graphs, but even so, $|V| > |E|$ is possible since a spanning tree may have as few as $|V| - 1$ edges. Though in this case, you would be correct to state that the runtime is $O(|E|)$ (but it is of course $O(|V|)$ as well).