It's UWAweek 42 (2nd semester, week 12)

help2200

This forum is provided to promote discussion amongst students enrolled in CITS2200 Data Structures and Algorithms.

Please consider offering answers and suggestions to help other students! And if you fix a problem by following a suggestion here, it would be great if other interested students could see a short "Great, fixed it!"  followup message.

How do I ask a good question?
Displaying selected article
Showing 1 of 176 articles.
Currently 6 other people reading this forum.


 UWA week 22 (1st semester, study break) ↓
SVG not supported

Login to reply

👍x1
helpful
3:37pm Fri 31st May, ANONYMOUS

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))?

The University of Western Australia

Computer Science and Software Engineering

CRICOS Code: 00126G
Written by [email protected]
Powered by history
Feedback always welcome - it makes our software better!
Last modified  8:08AM Aug 25 2024
Privacy policy