GATE Overflow Test Series | Algorithms | Test 2 | Question: 17

Question

Which of the following statements is/are TRUE with respect to the time complexities of the graph algorithms to find Minimum Spanning Trees? (Mark all the appropriate choices)

• A. Kruskal's algorithm to find MST runs in $O(|E| \lg |V|)$
• B. Prim's algorithm to find MST implemented using binary min-heap runs in $O(|E| \lg |V|)$
• C. Prim's algorithm to find MST implemented using Fibonacci heap runs in $O(|E| + |V| \lg |V|)$
• D. If graph is given in adjacency list form, Prim's algorithm to find MST runs in $\Theta(V^2)$ using binary min-heap

Answer 1

Options A,B,C are true. Option D is false, as adjacency list is the best representation for Prim's algorithm and it gives time complexity as $O(|E| \lg |V|)$ using binary min-heap. With Adjacency matrix representation, Prim's algorithm using binary min-heap runs in $O(|V|^2\lg |V|)$ time as now processing the adjacency list for each vertex takes $O(|V|)$ time.

Comments

Sir, please avoid Fibonacci heap related statements as only binary heap is there in the syllabus.

---

Sir I think option C is wrong as Prim's algorithm to find MST implemented using Fibonacci heap runs in O(|E|+logV).

---

@Sanandan No, c is correct.

In Fibonacci heap, EXTRACT_MIN takes O(log V) times and DECREASE_KEY takes O(1).

So, Overall time complexity is O(V*(logV) + E * (1) = O (V (logV) + E)

---

Prims is O((V+E).Log(V))

Is it okay to omit V.Log(V) from above asymptotic bound because E >= V?

Then if a question asks for time complexity of BFS/DFS, and gives an option of O(E), instead of O(E+V), is it correct?

Please help