# 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).