> Hello, > > I have watched the lectures and still do not understand why Kruskal's is (m+n)log n. Please clarify how the complexity arises. > > If there are m edges in the priority queue with m-weights, total cost of priority queue operations should be m*log(m). There are n clusters to begin with, and merging clusters takes log(n) since each cluster is at least doubled when merged, so the merging operations has n*log(n) complexity. > > So how come in the slides it says O((m+n)log(n)) and not O(m*log(m))?