Question

9. Indicate the runtime complexity of Dijkstra's algorithm when the implementation is not based on a binary min-heap.

Answer 1

The Dijkstra algorithm when implemented using a simple array instead of a binary min-heap, the time complexity is different.

The 2 main operations in the Dijkstra algorithm are :

• Extract Min
• Decrease Key

The number of times Extract Min operation takes place in the algorithm is O(V).

The number of times Decrease Key operation takes place in the algorithm is O(E).

Using an array, the Extract Min operation will take O(V) times as the array is usually unsorted and the minimum element has to be found out by scanning every vertex in the worst case.

So, total time taken for the Extract Min operation is = O(V) * O(V) = O(V^2).

Using an array, the Decrease Key operation will take O(1) time because in an array, an element can be directly accessed and its value can be decreased at constant time.

So, total time taken for the Decrease Key operation is = O(E) * O(1) = O(E).

Total time taken in the implementation of Dijkstra algorithm using an array is = O(V^2) + O(E).

In the worst case, O(E) = O(V^2) which happens if the graph is a complete graph.

So, total time to implement the Dijkstra algorithm using an array is = O(V^2) + O(E) = O(V^2) + O(V^2) = O(V^2).

Hence, the runtime complexity of Dijkstra's algorithm when the implementation is not based on a binary min-heap is O(V^2).