4,132 views
3 votes
3 votes
What is the time complexity to implement Dijkstra’s algorithm using a sorted array instead of heap for a Priority Queue?

for sorted array

let V be the number of nodes and E be the number of edges

1)extract min operation ---it will take constant time and it is repeated for V nodes.hence takes O(v) time.

2)decrease key operation occurs E times------now we can directly go and decrease the value of the node but we might have to sort the array again because after decreasing the key,array might not be sorted..so it will take VlogV time if we use merge sort.so ,total time is E*VLOGV

 

please verify this.

1 Answer

Best answer
12 votes
12 votes

................

selected by

Related questions

2 votes
2 votes
1 answer
1
yes asked Oct 6, 2015
1,329 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
8 votes
8 votes
2 answers
2
0 votes
0 votes
1 answer
4
iarnav asked Jun 12, 2018
839 views
Given an sorted array in descending order, what will be the time complexity to delete the minimum element from this array?