in Algorithms
231 views
1 vote
1 vote
What is Dijkstra's algorithm running time using sorted array?
in Algorithms
231 views

1 comment

Tem is O(1) but Tdk =??
0
0

2 Answers

0 votes
0 votes
O(V^3) in the worst case.
0 votes
0 votes
The total time complexity of Dijkstra’s Algorithm is given by : E.T(update key / relaxing edges) + V.T(to delete min) .
Where E is the edge and V denotes the vertices. T represents the time to implement the operation given in parenthesis.

The minimum in a sorted array is present at the first position itself (I am assuming an ascending sorted array) hence  the time is O(1) . Whereas the time required to update the key will be O(V). [The number of vertices in the array.]

Therefore we get the time as V+EV which can be taken as EV.

Please correct me If I am wrong.

Related questions