CS 577 Midterm 1 Prep / Complexity of Some Algorithms

During the preparation for the CS 577 Midterm, I find that it may be helpful if I list the complexity of some algorithms.

  • Dijkstra – \(O((n+m)\log n)\) (using adjacency lists and priority queues)
  • Topological Sort – \(O(n)\)

Also, solution to Question 7 in the practice problems (see also this file, and this better one, also a better problem statement by Jeff Erickson).

Solution in part (a) of Question 9 turns out to be essentially finding median of an array in linear time. See this amazing blog post (and this, too).

Last Updated on

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.