[SOLVED] Complexity of Prims Algorithm using Priority Queue?

Complexity of Prims Algorithm using Priority Queue?

I am using an adjacency matrix, priority queue is the data structure.

By my calculation, complexity is V^3 log V:

While loop: V
Checking adjacent Vertices: V
Checking the queue if the entry is already present, and updating the same: V log v

But, I read everywhere that the complexity is V^2

Please explain.

Solution

If you use a Fibonacci heap, then extracting the min is O(lg V) amortized cost and updating an entry in it is 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)

Assume that the implementation has constant time for both priorityQueue.contains(v) and needsWeightReduction(u, v).

Something to note is that you can bound slightly tighter for checking adjacencies. While the outer loop runs V times, and checking the adjacencies of any single node is at worst V operations, you can use aggregate analysis to realize that you will never check for more than E adjacencies(because theres only E edges). And E <= V^2, so this is a slightly better bound.

So, you have the outer loop V times, and the inner loop E times. Extracting the min runs V times, and updating an entry in the heap runs E times.

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

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

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

But this is a looser bound when considering sparse graphs(although correct).