It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?
$O(m+n)$ really necessary for graph algorithms?
ds.algorithms;terminology;asymptotics