Dijkstra Time Complexity using Binary Heap

Question

Let G(V, E)be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

 1. O(|V|^2)
 2. O(|E|+|V|log|V|)
 3. O(|V|log|V|)
 4. O((|E|+|V|)log|V|)

========================================================================

Correct answer is -

4. O((|E|+|V|)log|V|)

=========================================================================

My Approach is as follows -

O(V+V+VlogV+ElogV) = O(ElogV)

• O(V) to intialize.
• O(V) to Build Heap.
• VlogV to perform Extract_Min
• ElogV to perform Decrease Key

Now, as I get O(ElogV) and when I see options, a part of me says the correct one is O(VlogV) because for a sparse Graph |V| = |E|, but as I said the correct answer is O((|E|+|V|)log|V|). So, where am I going wrong?

Answer 1

Well, you are correct that the complexity is actually O(E log V).

Since E can be up to (V^2 - V)/2, this is not the same as O(V log V).

If every vertex has an edge, then V <= 2E, so in that case, O(E log V) = O( (E+V) log V). That is the usual case, and corresponds to the "correct" answer.

But technically, O(E log V) is not the same as O( (E+V) log V), because there may be a whole bunch of disconnected vertexes in V. When that is the case, however, Dijkstra's algorithm will never see all those vertexes, since it only finds vertexes connected to the single source. So, when the difference between these two complexities is important, you are right and the "correct answer" is not.