4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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|)$)? $\endgroup$ – salcc Aug 7 at 14:08
  • $\begingroup$ Not because it's a tree but, rather, because a connected graph must have at least as many edges as a tree. But you're right that the same argument can be applied to any algorithm on connected graphs, including BFS. $\endgroup$ – David Richerby Aug 7 at 14:23
  • $\begingroup$ 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)... $\endgroup$ – salcc Aug 7 at 14:31
  • $\begingroup$ @salcc BFS is O(V+E) in adjacency list format because 1) each vertex is put onto the queue only once, giving O(V) operations and 2) across the loop, each edge is visited exactly twice in an undirected graph (eg: if there's an edge (u,v), it is visited once in u's list and once in v's list), so making it O(2E) which is O(E) operations. So in total, the time complexity comes out as O(V+E). $\endgroup$ – Gokul Aug 7 at 14:59
  • 2
    $\begingroup$ @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. $\endgroup$ – David Richerby Aug 7 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.