CODEWITHSUNDEEP
algorithmgraph
thinkdeep
thinkdeep

Reputation: 1033

Complexity of Dijkstra's Algorithm for Heap Implementation

In CRLS' book, the analysis of Dijkstra's algorithm is as follows:

How many times do you need to use the heap? One time for pulling off each node from the heap (i.e. Extract-Min in CRLS's book) --- O(N); and also every time when looking at the edge ---- O(E), you might need to change the distance (i.e., Decrease-Key in CRLS' book), which means to fix the heap order. And each heap operation needs O(logN) work.

Thus, total time complexity: O((N + E)logN), which is O(ElogN) if all vertices are reachable from the source.

My Question is: Why the complexity becomes O(ElogN) if all vertices are reachable from the source? Why can we ignore the O(NlogN) part from O((N + E)logN)?

Upvotes: 1

Views: 192

Answers (2)

Henry
Henry

Reputation: 43738

If all nodes are connected there must be at least N-1 edges. So E >= N-1 and thus N <= E+1 and N+E <= 2E+1 which is in O(E).

Upvotes: 2

mingaleg
mingaleg

Reputation: 2087

If all vertices are reachable from the source, then there are at least N-1 edges in graph, therefore E >= N-1, N = O(E) and O((N + E) log N) = O((E + E) log N) = O(E log N)

Upvotes: 2

Related Questions