Time Complexity of Prims Algorithm?
prims-algorithm, time-complexity
Solution
MST-PRIM(G, w, r)
1 for each u ∈ G.V
2 u.key ← ∞
3 u.π ← NIL
4 r.key ← 0
5 Q ← G.V
6 while Q ≠ Ø
7 u ← EXTRACT-MIN(Q)
8 for each v ∈ G.Adjacent[u]
9 if v ∈ Q and w(u, v) < v.key
10 v.π ← u
11 v.key ← w(u, v)
Using a Binary Heap
The time complexity required for one call to `EXTRACT-MIN(Q)` is `O(log V)` using a min priority queue. The while loop at line 6 is executing total V times.so `EXTRACT-MIN(Q)` is called `V` times. So the complexity of `EXTRACT-MIN(Q)` is `O(V logV)`.
The `for` loop at line 8 is executing total `2E` times as length of each adjacency lists is `2E` for an undirected graph. The time required to execute line 11 is `O(log v)` by using the `DECREASE_KEY` operation on the min heap. Line 11 also executes total `2E` times. So the total time required to execute line 11 is `O(2E logV) = O(E logV)`.
The `for` loop at line 1 will be executed `V` times. Using the procedure to perform lines 1 to 5 will require a complexity of `O(V)`.
Total time complexity of `MST-PRIM` is the sum of the time complexity required to execute steps 1 through 3 for a total of `O((VlogV) + (E logV) + (V)) = O(E logV)` since `|E| >= |V|`.
Using a Fibonacci Heap
- Same as above.
- Executing line 11 requires `O(1)` amortized time. Line 11 executes a total of `2E` times. So the total time complexity is `O(E)`.
- Same as above
So the total time complexity of `MST-PRIM` is the sum of executing steps 1 through 3 for a total complexity of `O(V logV + E + V)=O(E + V logV)`.
Problem
I found the time complexity of Prims algorithm everywhere as O((V + E) log V) = E log V. But as we can see the algorithm: It seems like the time complexity is O(V(log V + E log V)). But if its time complexity is O((V + E) log V). Then the nesting must have to be like this: But the above nesting is seems to be wrong.