Register

#Algorithms Kruskal Algorithm for MST Doubt.
closed

• closed by
645 views
0 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?

Voting & Accepting an answer helps improve the community
← Previous · ISI-SAMPLE-2014-22Next → · what is the differen...
← Previous in category · Solve the RecurrenceNext in category → · #Algorithms MST Ques...
Position:
Show:

Related questions

1 1 vote
1 1 answer
917
917 views
rahul sharma 5 asked Sep 27, 2017
917 views
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
2 2 votes
1 answers 1 answer
2.1k
2.1k views
iarnav asked Apr 11, 2018
2,131 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 ...
1 1 vote
0 0 answers
1.4k
1.4k views
Shivam Chauhan asked Nov 2, 2017
1,436 views
MST Kruskal
First statement is False because complexity will be O(E2).I think the second statement is true? But not sure
0 0 votes
3 3 answers
3.0k
3.0k views
iarnav asked Apr 29, 2018
3,022 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?