Understanding Time complexity calculation for Dijkstra Algorithm

Question

As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to understand it step by step.

1. Each vertex can be connected to (V-1) vertices, hence the number of adjacent edges to each vertex is V - 1. Let us say E represents V-1 edges connected to each vertex.
2. Finding & Updating each adjacent vertex's weight in min heap is O(log(V)) + O(1) or O(log(V)).
3. Hence from step1 and step2 above, the time complexity for updating all adjacent vertices of a vertex is E*(logV). or E*logV.
4. Hence time complexity for all V vertices is V * (E*logV) i.e O(VElogV).

But the time complexity for Dijkstra Algorithm is O(ElogV). Why?

Wooster

Answer 1

Dijkstra's shortest path algorithm is O(ElogV) where:

• V is the number of vertices
• E is the total number of edges

Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV) where:

• V is the number of vertices
• E is the maximum number of edges attached to a single node.

Let's rename your E to N. So one analysis says O(ElogV) and another says O(VNlogV). Both are correct and in fact E = O(VN). The difference is that ElogV is a tighter estimation.

Homburg

thanks, got your point, adjacentEdges*totalVertices = totalEdges(E). but can you throw some light on what a tighter bound/estimation really means. – Wooster

@MeenaChaudhary, more precisely maxAdjacentEdgesOfAVertex * totalVertices >= totalEdges, and that's what gives the tighter bound. A tighter bound means an estimate closer to the truth. For example, if an algorithm performs n + 10 operations, you can say it's O(n^2) which is true, or O(nlogn) which is also true. But it's also O(n) which is a tighter bound than those other two. The tightest bound possible is called Θ, so in the above example n + 1 = Θ(n). (The definition of Θ is what is both an upper and a lower bound) – Homburg

@Homburg Just to be clear, you mean E*log[2](V), (log with base 2) correct? Which comes from assuming a binary heap to help keep track of things? – Commonable

@SeldomNeedy, Yes, that's log in base 2. Although as long as the O notation is concerned, it doesn't make a difference, because log[10](V) = log[10](2)*log[2](V), so the difference is only in a constant, which doesn't change the time order of the algorithm. – Homburg

@SeldomNeedy, oh, and with computer algorithms, you seldom need log in any base other than 2, so base 2 is kind of implied. (See what I did there?) – Homburg

We can also mention that we get this complexity when the graph is sparse. For dense graphs, maximum edges (E) can be V(V-1)/2, hence complexity: O((V + V^2) logV) – Gayla

Is this time complexity or running time ? – Contemptible

I want to point out that this time complexity, O(E log V), assumes the given graph is connected. In the case of a sparse graph that has a lot of lone vertices, for example, it will not hold. That is why the worst case for Dijkstra binary heap implementation is O(V log V + E log V). When we cannot assume E >= V , it cannot be reduced to O(E log V) – Baklava

+like nice answer. one question. at each step we have O|E| update in worst case in dijkestra, am I right why? I means if we want say amortized cost of update can we say what? O(|E| / |N| )? – Toliver

Answer 2

Adding a more detailed explanation as I understood it just in case:

• O(for each vertex using min heap: for each edge linearly: push vertices to min heap that edge points to)
• V = number of vertices
• O(V * (pop vertex from min heap + find unvisited vertices in edges * push them to min heap))
• E = number of edges on each vertex
• O(V * (pop vertex from min heap + E * push unvisited vertices to min heap)). Note, that we can push the same node multiple times here before we get to "visit" it.
• O(V * (log(heap size) + E * log(heap size)))
• O(V * ((E + 1) * log(heap size)))
• O(V * (E * log(heap size)))
• E = V because each vertex can reference all other vertices
• O(V * (V * log(heap size)))
• O(V^2 * log(heap size))
• heap size is V^2 because we push to it every time we want to update a distance and can have up to V comparisons for each vertex. E.g. for the last vertex, 1st vertex has distance 10, 2nd has 9, 3rd has 8, etc, so, we push each time to update
• O(V^2 * log(V^2))
• O(V^2 * 2 * log(V))
• O(V^2 * log(V))
• V^2 is also a total number of edges, so if we let E = V^2 (as in the official naming), we will get the O(E * log(V))

Palestine

Very well put!! – Homebrew

@sam can you explain this part ""E = V because each vertex can reference all other vertices" – Maxilliped

@MrA if you have vertices A,B,C then A can connect to B and C. And B can connect to A and C. And C can connect to A and B. So any vertex can connect to V - 1 total vertices (except itself), so there can be V - 1 edges on each vertex, which is basically equal to V. So, E = V – Palestine

Nicely explained! One quick question - is there a reason why we simplify O(V^2 * log(V^2)) to O(E*log(V)) instead of O(E*log(E))? I understand the math behind it, but not the reasoning. – Carlenacarlene

@Carlenacarlene technically O(E*log(E)) is correct also but O(E*log(V)) is more accurate. And the OP asked about O(E*log(V)) specifically, so in this context we have to finish with this. – Palestine

@Palestine Thank you! – Carlenacarlene

O(for each vertex using min heap: for each edge linearly: push vertices to min heap that edge points to) V = number of vertices O(V * (pop vertex from min heap + find unvisited vertices in edges * push them to min heap)) why is number of nodes using min heap = V? shouldn't it be V^2? – Transmogrify

@Transmogrify not sure what you mean sorry – Palestine

Thank you so much for this. I was confused about the time complexity for so long. – Hemophilia

Answer 3

let n be the number of vertices and m be the number of edges.

Since with Dijkstra's algorithm you have O(n) delete-mins and O(m) decrease_keys, each costing O(logn), the total run time using binary heaps will be O(log(n)(m + n)). It is totally possible to amortize the cost of decrease_key down to O(1) using Fibonacci heaps resulting in a total run time of O(nlogn+m) but in practice this is often not done since the constant factor penalties of FHs are pretty big and on random graphs the amount of decrease_keys is way lower than its respective upper bound (more in the range of O(n*log(m/n), which is way better on sparse graphs where m = O(n)). So always be aware of the fact that the total run time is both dependent on your data structures and the input class.

Pubilis

Answer 4

In dense(or complete) graph, E logV > V^2

Using linked data & binary heap is not always best.

That case, I prefer to use just matrix data and save minimum length by row.

Just V^2 time needed.

In case, E < V / logV.

Or, max edges per vertex is less than some constant K.

Then use binary heap.

Klansman

Answer 5

I find it easier to think at this complexity in the following way:

1. The nodes are first inserted in a priority queue and then extracted one by one leading to O(V log V).
2. Once a node is extracted, we iterate through its edges and update the priority queue accordingly. Note that every edge is explored only once, moreover, updating the priority queue is O(log V), leading to an overall O(E log V).

TLDR. You have V extractions from the priority queue and E updates to the priority queue, leading to an overall O((V + E) log V).

Eyebolt

This assumes number of nodes in a priority queue is V. But we can push the same node multiple times before we get to "visit" it, which is more like E but not V? How did you make this assumption? – Transmogrify

You can refer to the following implementation: geeksforgeeks.org/…. In particular, nodes are never added twice to the minheap, instead, their weight is updated and their position in the minheap is also updated accordingly. – Eyebolt

@Transmogrify actually you are right heap size can grow with max bound no of edges that is v(v-1) which is v^2. But log(v^2) is l2*log(v) that is log(v) in the end – Charlettecharley

Answer 6

• E is edges and V is vertices. Number of edges

   (V *(V-1)) / 2
  

approximately

    V ^ 2

• So we can add maximum V^2 edges to the min heap. So sorting the elements in min heap will take

   O(Log(V ^ 2))
  

• Every time we insert a new element into min heap, we are going to sort. We will have E edges so we will be sorting E times. so total time complexity

  O(E * Log(V ^ 2)= O( 2 * E * Log(V)) 
  

Omitting the constant 2:

 O( E * Log(V)) 

Xerophthalmia

1) Though, the answer doesn't change, it is better if the time complexity of removal of nodes from min heap is also considered. V nodes are removed if the problem is about SSSP for a single node and E nodes if it is about SSSP for all nodes from a source node. Sorting here is same, O(logE). 2) Also E = V^2 for connected and dense graph and V for connected and sparse graph. Not sure of disconnected graph (maybe 0 where all nodes don't have any edges and are a graph in itself) – Guadiana

Answer 7

Let's try to analyze the algorithm as given in CLRS book.

for each loop in line 7: for any vertex say 'u' the number of times the loop runs is equal to the number of adjacent vertices of 'u'. The number of adjacent vertices for a node is always less than or equal to the total number of edges in the graph.

If we take V (because of while loop in line 4) and E (because of for each in line 7) and compute the complexity as VElog(V) it would be equivalent to assuming each vertex has E edges incident on it, but in actual there will be atmost or less than E edges incident on a single vertex. (the atmost E adjacent vertices for a single vertex case happens in case of a star graph for the internal vertex)

Galcha

Answer 8

V:Number of Vertices, E:Number of total_edges Suppose the Graph is dense The complexity would be O(V*logV) + O( (1+2+...+V)*logV)

1+2+....+(V-1) = (v)*(v+1)/2 ~ V^2 ~ E because the graph is dense So the complexity would be O(ElogV).

The sum 1+2+...+ V refers to: For each vertex v in G.adj[u] but not in S If you think about Q before a vertex is extracted has V vertices then it has V-1 then V-2 ... then 1.

Amiss