# What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $$O(|V|\log|V|+|E|\log|V|)$$ and I understand why. But then it says that $$O(|V|\log|V|+|E|\log|V|) = O(|E|\log|V|)$$, because $$|V|=O(|E|)$$. What does $$|V|=O(|E|)$$ mean and why is it so?

First, $$|V|$$ is the number of vertices and $$|E|$$ is the number of edges.
The point is that if a graph is connected it must have at least $$|V|-1$$ edges. Therefore, $$|V|\leq |E|+1$$, so $$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$
Writing $$|V|=O(|E|)$$ is something of an abuse of notation. $$O(\cdot)$$ is an asymptotic statement about what happens as some variable becomes large, over some infinite family of instances. So, here, we're supposed to imagine that the infinite family of instances is the set of all connected finite graphs. It would have been clearer to just write $$|V|\leq |E|+1$$.
• Ok, thanks for the correction, now I think that I understand it. But one question, if we can reduce $O(|V|\log|V|+|E|\log|V|)$ to $O(|E|\log|V|)$, because we can use the fact that it's a tree so $|V|\leq |E|+1$, why is the time complexity of breadth-first search $O(|V|+|E|)$? Couldn't we reduce it to $O(|E|)$ by doing something similar ($|V|+|E|\leq 3|E|$, so $O(|E|)$)? – salcc Aug 7 at 14:08
• But then is there any reason why in many places it says that BFS is $O(|V|+|E|)$? For example CLRS 3rd Ed., p. 597, the previous Stanford lecture to the one linked on the question (web.stanford.edu/class/archive/cs/cs106b/cs106b.1198/lectures/…, p. 64), Wikipedia (en.wikipedia.org/wiki/Breadth-first_search)... – salcc Aug 7 at 14:31
• @Gokul But BFS only visits the vertices in the component that takes the start vertex and there are at most $|E|+1$ vertices in that component. The actual reason is quite subtle, so I put it in its own question. – David Richerby Aug 7 at 15:30