help2200

It's UWAweek 47

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 the 6 articles in this topic

Showing 6 of 176 articles.
Currently 9 other people reading this forum.

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

Kruskal Union Time Complexity (all 6)

9:44pm Wed 29th May, ANONYMOUS

Hey, looking back on lecture material, for kruskals algorithm the complexity is O((n+m)log(n)), where n = vertices and m = edges. It states that all the MST union operations result in complexity of nlog(n), but I can't find where this is explained, as appearance of log(n) always suggests some halving shenanigans that to my knowledge aren't expanded upon in the lectures. Doing some online research results in different interpretations. Just want some clarification how I should explain the complexity of the union MST operation part of Kruskal's algorithm if it comes up in exam.

Kruskal Union Time Complexity (all 6)

12:51pm Thu 30th May, Hugo S.

I also have a question which links onto this one, if we are explaining the time complexity of Kruskal's, do we talk about the inverse Ackermann function?

Kruskal Union Time Complexity (all 6)

4:06pm Thu 30th May, Amitava D.

"Hugo Smith" <23*2*1*2@s*u*e*t*u*a*e*u*a*> wrote:

> I also have a question which links onto this one, if we are explaining the time complexity of Kruskal's, do we talk about the inverse Ackermann function?

No, we did not do any such complicated thing. I have explained the complexity in a very simple way. When we do the union operation, we double at least one of the sets by the union. Since it is true in every step, we need O(log n) steps. Please listen to the lecture on Kruskal's algorithm.

Kruskal Union Time Complexity (all 6)

12:36pm Fri 31st May, ANONYMOUS

I would also like to know what the first student asked: Hey, looking back on lecture material, for kruskals algorithm the complexity is O((n+m)log(n)), where n = vertices and m = edges. It states that all the MST union operations result in complexity of nlog(n), but I can't find where this is explained, as appearance of log(n) always suggests some halving shenanigans that to my knowledge aren't expanded upon in the lectures.//// this is what I found in the lecture but couldn't find anything else on getting closer to nlogn: Partition-Based Implementation  Partition-based version of Kruskal’s Algorithm  Cluster merges as unions  Cluster locations as finds  Running time O((n + m) log n)  Priority Queue operations: O(m log n)  Union-Find operations: O(n log n) Thank you

Kruskal Union Time Complexity (all 6)

12:58pm Fri 31st May, ANONYMOUS

Nvm, I was acutually thinking about Dijkstra’s Algorithm not Kruskal’s, been struggling getting to nlogn. The best achievable complexity with my given approach is 𝑂 ( ( 𝑛 + 𝑚 ) log ⁡ 𝑛 ), which is close but not strictly 𝑂 ( 𝑁 log ⁡ 𝑁 ) this is for security_routing.py

Kruskal Union Time Complexity (all 6)

9:04pm Fri 31st May, Amitava D.

ANONYMOUS wrote:

> I would also like to know what the first student asked: Hey, looking back on lecture material, for kruskals algorithm the complexity is O((n+m)log(n)), where n = vertices and m = edges. > > It states that all the MST union operations result in complexity of nlog(n), but I can't find where this is explained, as appearance of log(n) always suggests some halving shenanigans that to my knowledge aren't expanded upon in the lectures.//// > this is what I found in the lecture but couldn't find anything else on getting closer to nlogn: > > Partition-Based > Implementation >  Partition-based version of > Kruskal’s Algorithm >  Cluster merges as unions >  Cluster locations as finds >  Running time O((n + m) log n) >  Priority Queue operations: O(m log n) >  Union-Find operations: O(n log n) > > Thank you

Could not understand your question.

help2200 articles all ANNOUNCEMENTS recent articles login to post a new article help2200 topics from today and yesterday from the past week from the past two weeks ALL topics, most recent first	login chapter0 unitinfo research projects csforum csse-feedback csbreakdown cssubmit csmarks 2nd semester help fora Algebra Advanced Algorithms Cloud Computing High Performance Computing Intelligent Agents Professional Computing Relational Database Management Systems Systems Programming