#Algorithms Time Complexity Analysis of Multistage Graph using Bottom Up Dynamic Programming

Question

Time complexity of Multistage Graph is O(n²) or O(V²) but then some people says it's O(E). So, from O(V²) to O(E) are they taking about dense/complete graphs in which number of edges |E| = |V²|?

Kindly help!

Comments

https://www.geeksforgeeks.org/multistage-graph-shortest-path/

---

Thanks, Ma'am @srestha.

Answer 1

In dense graph number of edges are => O(v^2)
thats why we say complexity in worst case will be O(E).

Answer 2

In a multi-stage graph algorithm for shortest path, we minimize cost for every edge exactly once. So the Time Complexity is $O(E)$. However, in the worst case, we get a complete graph, which has edges $E = n*(n-1)/2$​, so worst time complexity then becomes $O(E) = O(n^2).$

Note that in this case too, every edge is processed exactly once.

Comments

THANKS PAAJI