Hey there! Thanks for dropping by CS16: Algorithms and Data Structures! Take a look around and grab the RSS feed to stay updated. See you around!
Post your questions here!
Dijkstra’s step-by-step animation
« HW8 Posted
MST Lecture Posted »
The way it’s written in the slides is a little misleading, considering the way we breakdown runtimes for all the other algorithms. In this part, that inner loop does not access every edge for every vertex. The inner loop is O(|E|) because for each vertex we look at, we look at each of its outgoing edges. As a result, over the course of the algorithm, we end up looking at every edge once. This is O(|E|+|V|) (in addition to the time due to priorityqueue implemenetation).
That makes sense. Cheers!
On slides 35 and 36, the while loop is O(|v|) and the method to find all edges is O(|E|). Since the method to find all edges is inside the while loop, shouldn’t the runtime of those 2 alone(assuming everything else is O(1)) be O(|V||E|) instead of O(|V|+|E|) as is displayed on slide 36.
For instance, an array/LinkedList implementation of the PriorityQueue would then be O(|V|(|V| + |E|)) ie O(|V|^2 + |V||E|) and for the heap implementation it would be O(|V|log|V| + |V||E|log|V|).
You must be logged in to post a comment.