The Big O on the Dijkstra Fibonacci-heap solution

Question

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?

Answer 1

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.