###### Question 10668 – Time-Complexity

February 13, 2024###### Question 10494 – Time-Complexity

February 13, 2024# Question 10528 – Time-Complexity

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph

G with vertices and m edges has the time complexity of:

Correct Answer: F

Question 31 Explanation:

Though the edges are sorted still due to finding union operation complexity is O(m log n).

→ Where m is no. of edges and n is number of vertices then n = O(m

→ O(m logn) < O(mn)

→ Where m is no. of edges and n is number of vertices then n = O(m

^{2})→ O(m logn) < O(mn)

O(n

^{2})O(mn)

O(m+n)

O(m log n)

O(m

^{2}B, D and E

Subscribe

Login

0 Comments