0

the time complexity of dijkstra algorithm is O((V + E) logV)

if my graph is E < V like the image I attached below

graph

can I drop the E and simplify it to O(VlogV)?

If can, I would like to know why the E can be ignored?

1

1 Answer 1

3

If 𝐸 < 𝑉, then the expression 𝑉 + 𝐸 is less than 2𝑉. That coefficient is not significant for big O notation, so then O((𝑉 + 𝐸) log𝑉) = O(2𝑉log𝑉) = O(𝑉log𝑉).

Sign up to request clarification or add additional context in comments.

4 Comments

Even if E<2V, btw. Or E<1000000V. As long as we can state that, ∀V, E<kV. So, for example, if it is a road network graph, as long as you can say "whatever the size of the graph, even if we were to include in it future colonies in the Moon and on Mars, we are sure that E<10V — which sounds reasonable; I don't know any roundabout or cross-road with 10 roads connected, and even if there were one, I just need to say that on average, no graph has so many roads per nodes—, then, we can see in such a graph, that Dijkstra is O(V.log V)
Same goes (with maybe higher factor k) for graph about electrical network, or computer network, or water network,.... As long as you can say that the average number of edges per vertex does not increase. Most of the physical network act that way: when they become bigger, it is by adding new vertex, but not by adding more connection per vertex.
Counter example: most game theory graph. The graph of all possible position (vertices) of a game, connected by edges (possible moves), tends to increase when you increase the size of the problem, If you increases the size of the board and the number of pawn accordingly, of a chess board, then, not only the number of possible positions (V) increases, but the number of possible move per position (E/V) also increases. In that case, you can't say that DIjkstra is O(V.log V)
I think it should be noted that we have V <= V+E <= 2V, so that the equal sign in O((V+E) logV) = O(V log V) is really set equality and not just set inclusion; in other words, there is no "loss of information" by writing O(V log V) instead of O((V+E) log V) under the assumption E <= V.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.