Graph Theory37 sections · 1633 units
Open in Course

Quiz: Kruskal vs Prim on Dense Graphs

Knowledge check

Check Your Understanding

For dense graphs where E≈V2E \approx V^2, which algorithm has better time complexity?

  1. A.Kruskal, because sorting edges is efficient
  2. B.Prim, because O(Elog⁡V)O(E \log V) beats O(Elog⁡E)O(E \log E) when E≈V2E \approx V^2
  3. C.Both have the same time complexity on dense graphs
  4. D.Kruskal, because Union-Find operations are nearly O(1)O(1)
Start the roadmap to answer the quizzes and solve the challenges