help2200

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

Showing 4 of 176 articles.
Currently 4 other people reading this forum.

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

trains_planes time complexity (all 4)

2:04pm Mon 27th May, ANONYMOUS

hi, just wondering.. is anyone actually able to reach the time complexity of O(NlogN) in trains_planes? at the moment I am only able to reach a time complexity of O(AB) where A & B is the number of trains and planes respectfully.

trains_planes time complexity (all 4)

3:01pm Mon 27th May, Amitava D.

ANONYMOUS wrote:

> hi, just wondering.. is anyone actually able to reach the time complexity of O(NlogN) in trains_planes? at the moment I am only able to reach a time complexity of O(AB) where A & B is the number of trains and planes respectfully.

This is Dijkstra's algorithm that has a time complexity of O((V+E)log V) as covered in the lectures. Here N is V+E.

trains_planes time complexity (all 4)

8:07pm Mon 27th May, ANONYMOUS

Wouldn't dijkstra's algorithm need to be done for each iteration of planes though? So it would be (number of planes) * ((V+E)logV)?

trains_planes time complexity (all 4)

10:22am Tue 28th May, Amitava D.

ANONYMOUS wrote:

> Wouldn't dijkstra's algorithm need to be done for each iteration of planes though? > > So it would be (number of planes) * ((V+E)logV)?

You can do better without directly running Dijkstra's algorithm, by using set operations.

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