What is the time complexity of Dijkstra's algorithm using a binary heap for a graph with V vertices and E edges?

• A. O((V+E) log V)
• B. O(V log E)
• C. O(V^2)
• D. O(E log V)

Answer: (A)

Using a binary heap for the priority queue, Dijkstra's algorithm spends O(log V) time for each heap operation. It performs a heap extraction for every vertex (V times) and up to one heap operation per edge when relaxing edges (up to E times). Multiply these: (V + E) heap operations, each taking O(log V), giving a total time of O((V + E) log V). This bound accounts for both the vertex processing and the edge relaxations, which is why it’s the most accurate general description. In sparse graphs this often behaves like O(V log V), while in very dense graphs E dominates and the bound reflects that through the E term.