[CROSSTALK] >> All right, in this concept challenge, we're gonna look at Dijkstra's Algorithm. And we're gonna do some runtime analysis. So you'll need your big o skills out and ready for this concept challenge. You know the drill. I'm not gonna dwell on it. You'll have a couple chances to answer the question. And you'll get to see the UCSD learners discussing. And you'll get to hear our explanation. So here's your question. Here's Dijkstra's algorithm as Leo presented it. And the question we have for you is, what is the running time of this algorithm in terms of the number of edges and the number of vertices in the graph? >> Hi, my name is Wong. >> Hi, I'm Miguel. >> Hi, my name is Yu Mei. >> So let's get started. >> Okay. >> For this question, I don't think the answer should be A or E because durable is having score so long and it's too much. >> Yeah, I definitely agree. Just because it says for each of curr's neighbors n. So that's saying like oh, it's the edges between curr and n. >> Mm-hm. >> So we're working with the edges and not the vertices. >> Mm. >> I think the answer is C. if you look at the while loop, he loops through every single edges. And in sides of loop we're popping from the queue which takes about off n and that n in this case is edge E, right? >> That's a good guess. But why don't we consider vertices which is D cuz C doesn't include V. >> Why do we need to include vertices? >> Mm, because that's talking about running time. We have to go over the vertices. >> Oh, we need to include vertices because we're adding all the vertices to the [LAUGH] priority queue first. >> Oh, that's right. I forgot about initialization. >> Now that you've watched the UCSD learners discuss the problem and thought about it, let's go over the answer here. So the way we solve a big o problem is of course we're just gonna trace to the code and think about all the steps that need to be done and how long they take. So let's start with the very first step. This initialization step. And if you think about the initialization, a lot of these steps are very fast but there's one that's gonna take a little bit longer. So what we have to do in the beginning is we have to set all of the distances in our graph to infinity. So we had to set that distance on every single node. So it's going to take order the number of vertices or nodes in the graph. So that's how long that first step is gonna take. Then we go on to the next step in the graph and we can see that that's a constant time operation. So how do these two steps combine? Let's just take a moment and pause and think about how these first two steps combine before we move forward. So whenever we have two steps that execute in sequence in an algorithm, you do one after the other. Then you're just gonna add together the running times to figure out the total running time. So at this point, we would have a running time of the sides, the number of vertices in the graph plus 1. But of course you know that o of the number of vertices in the graph plus 1 is just equal to o of the number of vertices in the graph so we don't really need that plus 1 at all. Consequently, we can kind of disregard this line that only took one operation as well. So we're just gonna omit that from our analysis for now as well as omit explicitly counting any of the other lines that have just constant running time. So let's continue. Let's go down now, and now we're into the meat of the algorithm, this while loop that's going to keep doing something, keep doing stuff as long as the priority queue is not empty. So this is a really big question. How many times does this loop run? Well, for a clue, we need to figure out how many nodes go into this priority queue. How many entries, not just nodes but how many entries? Cuz as you remember, the entries are going to be nodes plus distances. And the same node with a different distance is going to be a different entry in this priority queue. So let's look at where these entries get end queued. It's down here, okay? So what exactly are we doing down here? Well if you look at where we are in the algorithm, we're in the for loop that's going away from a particular node finding its neighbors. And the neighbors are basically just the edges of a particular node. So effectively what we're doing is we're adding one entry for every edge in the graph. Because for every node we're exploring out along all of its edges to find the neighbors. So each edge will lead to a new entry in that priority queue. So that priority queue, that while loop then, is going to have running time order the number of edges in the graph, okay? So that's how many times this loop is going to run. But now we need to take into consideration how long does each iteration of the loop take in the worst case? So now we're gonna go inside the loop. And all of these costs are going to be multiplied by the number of times the loop runs. So most of these operations inside the loop have constant time. So I've grayed out all the operations to have constant time. So we can focus on the operations that may or may not need to be considered explicitly. So let's consider this first statement here. Dequeuing the note from the front of the queue. Well if you remember back to what Leo said about priority queues, dequeuing and enqueuing nodes in a priority queue. So if we go down here as well, can be done in log(N) time where N is the size of the priority queue. Well our priority queue could be, at worst, the number of edges in the graph. So the time it could take to enqueue or dequeue from or into that priority queue could be log of the number of edges in the graph. So that's gonna be our running time bound for these two steps of dequeuing and enqueuing into the priority queue. So now we're left with this for loop statement. And the question is, what should we do about it? Do we need to somehow account for it? Maybe multiply that enqueue operation by the number of times the for loop iterates? Well, in fact, we don't because we've already counted for this for loop's iterations where we talked about accounting for the overall iterations of the while loop. Because this for loop is basically just adding stuff to the priority queue. And it's the while loop that's gonna keep running while the priority queue is not empty. That's going to basically govern the total work that this part of the algorithm is doing. So this for loop here has already been accounted for in our total number of calculations of how many times this while loop is going to run. So we can for now disregard it. And then we get to the final answer here that the while loop in total, taking into account what it does in it's body, takes the number of edges times log of the number of edges. Putting that together with the first step of the initialization step, we get to that the total running time is order number of edges times log of number of edges plus the number of vertices in the graph. Now that's a fine answer but if you go look online, you might find that the answer is slightly different from what we just derived here. You'll probably see an answer that looks like the statement here at the bottom. That the running time is order of the number of edges times logarithm of vertices plus the number of vertices. So what just happened? How did we go from logarithm of edges to logarithm of vertices? Well as you may recall, the number of edges is equal to at most, in the worst case, the number of vertices squared. Well the number of vertices squared is inside a log term. So a log term will pull out the squared part and that'll just go away as a constant factor. And we' ll be left with the order number of edges times log of the number of vertices still plus the number of vertices. And that's it.
