What is the time complexity of both Prim's and Kruskal's algorithms?
- O(E log V)
- O(E^2)
- O(V log E)
- O(V^2)
The time complexity of Prim's algorithm is O(E log V), and the time complexity of Kruskal's algorithm is also O(E log V), where 'V' is the number of vertices and 'E' is the number of edges in the graph. Both algorithms achieve this complexity by using efficient data structures to manage the edges and prioritize the minimum-weight edges.
Loading...
Related Quiz
- In selection sort, what is the main operation performed in each iteration?
- Binary search operates by repeatedly dividing the _______ in half until the desired element is found or determined to be absent.
- The choice between AVL and red-black trees often depends on the _______ characteristics of the application and the _______ of the operations being performed.
- DFS is often implemented using _______ recursion or an explicit _______ data structure.
- Red-black trees ensure balance by enforcing _______ rules on the color of nodes during insertion and deletion operations.