CODEWITHSUNDEEP
algorithm
user13985180
user13985180

Reputation: 251

What is the time complexity of kruskal's algorithm for an adjacency matrix?

Is it O(eloge) or is it O(V^2) since the whole matrix has to be iterated over to retrieve the edges in order for them to be sorted?

Upvotes: 0

Views: 1698

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59323

It's O(V2 + E log E), because it takes O(V2) to find the edges, and O(E log E) to sort them.

Note that this is at least O(V2), but no more than O(V2 log E), and in the worst case of dense graphs it is the same as O(E log E), because V2 is O(E) in those cases.

Upvotes: 2

Related Questions