Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo

Question

Suppose that you implement Dijkstra’s algorithm using a priority queue algorithm that requires O(V ) time to initialize, worst-case f(V, E) time for each EXTRACT-MIN operation and worst-case g(V, E) time for each DECREASE-KEY operation. How much (worst-case) time does it take to run Dijkstra’s algorithm on an input graph G = (V, E)?.

Comments

They are modifying time complexity of Extract MIN and Decrease Key from O(log V) to f(V,E) and g(V,E) respectively

Now analyze your code

---

@Shaik Masthan Sir, It means

O((no. of vertex)( time for each EXTRACT-MIN operation) + (no. of edges)(time for each DECREASE-KEY operation))

i.e. O(V. f(V, E)  + E.g(V, E))

---

exactly.

Answer 1

O((no. of vertex)( time for each EXTRACT-MIN operation) + (no. of edges)(time for each DECREASE-KEY operation))

i.e. O( V. f(V, E)  + E.g(V, E) )

Answer 2

dijkstars algo complxity=O(initilization +extractmin no of vertex time +decrease key no of edges time )

   so according to question here complexity will be =O(V+V. V.f(V, E)+E. g(V, E))