The complexity of the Primma algorithm using the priority queue?

Question

I use the adjacency matrix, the priority is the data structure.

According to my calculations, the complexity is V^3 log V :

• While loop: V
• Checking adjacent vertices: V
• Check the queue if the entry is already present and update it: V log v

But I read everywhere that complexity is V^2

Explain, please.

Answer 1

If you use the Fibonacci heap, then the min extraction is O(lg V) amortized cost and updating the record in it O(1) amortized.

If we use this pseudo code

 while priorityQueue not empty u = priorityQueue.exractMin() for each v in u.adjacencies if priorityQueue.contains(v) and needsWeightReduction(u, v) priorityQueue.updateKeyWeight(u, v) 

Suppose the implementation has a constant time for priorityQueue.contains(v) and needsWeightReduction(u, v) .

Something that needs to be noticed is that you can bind a little more tightly to check for adjacency. While the outer loop runs V times, and checking for the adjacency of any single node in the worst case, V allows you to use aggregate analysis to understand that you will never check more than E snaps (because theres only E edges). And E <= V^2 , so it's a little better.

So, you have the outer loop V times, and the inner loop E times. The extraction of minutes is performed V times, and the update of the record on the heap is performed E times.

  V*lgV + E*1 = O(V lgV + E) 

Again, since E <= V^2 you can use this fact to replace and get

  O(V lgV + V^2) = O(V^2) 

But this is a looser binding when considering sparse graphs (albeit correct).

Answer 2

Using a mini-heap priority queue, the time complexity is O (ElogV).

As you said, the outer while loop is O (V), because it iterates over each vertex, since each has to be added to the MST once.

For each vertex considered in the while loop, the following two steps must be performed:

1. The next edge is selected to be added to the MST. According to the properties of the mini-heap priority queue, the root element will always be the smallest element. Therefore, selecting the next edge that has the lowest cost will be O (1) extraction of the root element. The remaining values ​​will need to be shifted after extraction in such a way as to maintain priority queue. Since the queue is a balanced binary tree, this shift can occur in O (logV) in the worst case.

2. The priority queue is being updated. The edges associated with the new vertex may need to update their costs in the queue, because now we will consider the costs associated with the edges between the newly added vertex and its neighbors (however, if they are neighbors of the previously added vertex over the edge with a lower cost, than the recently introduced edge, the cost will not be updated, because we are looking for minimal costs). Again, this will be O (logV), because in the worst case, the vertex must be shifted along the entire length of the balanced binary tree that the queue represents.

Step 1 is performed V times because it occurs once in the while loop, therefore it is equal to O (VlogV), and Step 2 is executed E times in the worst case, when each edge is attached to the current vertex, and therefore they must all be updated , which means that it is O (ElogV). The setting is O (E), because there must be infinity in the priority queue to initialize each edge cost.

Total time complexity using the priroty constant with minimal heap = O (E + VlogV + ElogV) = O (ElogV)

When you read that complexity is O (V ^ 2), you can look at implementations that don't use heaps. In this case, the outer while loop is still O (V). The bottleneck is in the step that selects the next vertex to add to the MST, which is O (V), because you will need to check the cost associated with each neighboring node to find the lowest cost, which in the worst case means checking all the others nodes, therefore the complexity is O (V * V) = O (V ^ 2).

In addition, O (ElogV) in very dense graphs becomes O (V ^ 2), because on any graph there can be a maximum of E = V ^ 2 common edges.