Register

#Algorithms Kruskal Algorithm for MST Doubt.
closed

• closed by
416 views
0 votes
0 votes
closed with the note: Coremen Helped!

Time Complexity of Kruskal - O(mlogm + n.O(1) + m.logn)

mlogm --> for sorting edges in increasing order.

n.O(1) --> n UNIONS as we've n nodes in G and each takes O(1)

m.logm --> Find operation takes logn time as height of tree can never me more than logn and we have m such find operations as we have m edges in G.

Now my doubt is - is it O(mlogm) or O(mlogn)? I know, given is O(mlogn), but how?

• closed by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
rahul sharma 5 asked Sep 27, 2017
565 views
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
User Avatar
1 votes
1 votes
1 answer
2
iarnav asked Apr 11, 2018
958 views
#Algorithms MST Question Doubt
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is - keeping all edge positive all the time), then is it TRUE or FALSE? Shortest path between any pair of vertices does not change?
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is - keeping all edge ...
User Avatar
1 votes
1 votes
0 answers
3
Shivam Chauhan asked Nov 2, 2017
755 views
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
First statement is False because complexity will be O(E2).I think the second statement is true? But not sure
User Avatar
0 votes
0 votes
3 answers
4
iarnav asked Apr 29, 2018
1,595 views
#Algorithms #MST Doubt in MST Questions.
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST?Question2 ) Prim's algorithm works with negative weighted edges?
User Avatar
Link Copied!