CODEWITHSUNDEEP
algorithmbig-odijkstra
Nikola
Nikola

Reputation: 2132

The Big O on the Dijkstra Fibonacci-heap solution

From Wikipedia: O(|E| + |V| log|V|)

From Big O Cheat List: O((|V| + |E|) log |V|)

I consider there is a difference between E + V log V and (E+V) log V, isn't there?

Because, if Wikipedia's one is correct, shouldn't it be shown as O(|V| log |V|) only then (Removing |E|) for a reason I do not understand?)?

What is the Big O of Dijkstra with Fibonacci-Heap?

Upvotes: 8

Views: 20572

Answers (2)

user3146587
user3146587

Reputation: 4320

The complexity of Dijkstra's shortest path algorithm is:

    O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)

where Q is the min-priority queue ordering vertices by their current distance estimate.

For both a Fibonacci heap and a binary heap, the complexity of the extract-min operation on this queue is O(log |V|). This explains the common |V| log |V| part in the sum. For a queue implemented with an unsorted array, the extract-min operation would have a complexity of O(|V|) (the whole queue has to be traversed) and this part of the sum would be O(|V|^2).

In the remaining part of the sum (the one with the edge factor |E|), the O(1) v.s. O(log |V|) difference comes precisely from using respectively a Fibonacci heap as opposed to a binary heap. The decrease key operation which may happen for every edge has exactly this complexity. So the remaining part of the sum eventually has complexity O(|E|) for a Fibonacci heap and O(|E| log |V|) for a binary heap. For a queue implemented with an unsorted array, the decrease-key operation would have a constant-time complexity (the queue directly stores the keys indexed by the vertices) and this part of the sum would thus be O(|E|), which is also O(|V|^2).

To summarize:

  • Fibonacci heap: O(|E| + |V| log |V|)
  • binary heap: O((|E| + |V|) log |V|)
  • unsorted array: O(|V|^2)

Since, in the general case |E| = O(|V|^2), these can't be simplified further without making further assumptions on the kind of graphs dealt with.

Upvotes: 23

Roam
Roam

Reputation: 4949

Dijkstra's is O(|E| + |V| log|V|) with Fibonacci heap and O((|V| + |E|) log |V|) without it.

Both correct in some way. Big O Cheat List showing the most common implementation and Wiki the best there is.

O(|E| + |V| log|V|) isn't in O(|V| log|V|) btw. E is in O(|V|^2), not O(|V| log|V|).

Upvotes: 0

Related Questions