CODEWITHSUNDEEP
algorithmgraphtime-complexity
Daniel
Daniel

Reputation: 1554

what is the time complexity of Dijikstra using min binary heap but without update function

When using Dijkstra's algorithm to solve single source shortest path problem, a common solution is to use binary minheap with update operation. The consensus for time complexity is O((E+V)log(V)), because the heap size is capped at V due to availability of update, and there are E update and V extractMin operations both with complexity logV.

However, there're also solutions that simply add new priority/distance node into the priority queue, because updating a priority queue is not present in many languages such as c++ and python. In this scenario, the heap size is not constant at V. What is the time complexity then? My guess is O(E log E), because each node is inserted into the priority queue for E times, and in add operation, there could be as many as E records already in the queue so the add operation itself is logE, combined with E loops, the overall complexity is O(ElogE).

Am I right in this thinking?

Upvotes: 0

Views: 264

Answers (1)

Cătălin Frâncu
Cătălin Frâncu

Reputation: 1199

That is correct. I found a good analysis here (read past the C++ code, the discussion beginning with "Note that it is possible to use C++ built-in heaps...").

It is worth noting that O(log E) = O(log V) because E < V2 and therefore log E < 2 log V. So the asymptotic time complexity does not change. Having said that, in my experience the code tends to run more slowly because the heap is larger. On the plus side, the code is shorter and clearer, because you no longer need the ability to run decrease_key() and therefore you no longer need pointers into the heap for finding nodes quickly.

Upvotes: 1

Related Questions