0:00

So now that we have the algorithm BFS and we argued,

Â we showed how it works and we argued that it is correct.

Â We looked at the distances it computes and they make sense.

Â The question is, again it takes us back to the question, is it efficient?

Â We have seen brute force algorithm for

Â computing distances, we analyzed the surrounding time, it didn't look good.

Â We said this is not feasible.

Â Now we have come up with another algorithm that is simple, the question is,

Â is it efficient?

Â 0:28

The next thing we need to do is to try to understand the efficiency of

Â this algorithm.

Â So, we will look at this algorithm and

Â try to analyze its running time and see how long it takes.

Â As again as we showed before is that when we have the algorithm the first thing we

Â should do is number the lines, and start thinking about how long each line takes.

Â Okay?

Â And before we start analyzing these the, the running time,

Â we have to answer a few questions.

Â Remember, that we now to talk about a specific implementation, and,

Â because we need to understand how this operations are going to be performed.

Â So the first thing we are going to assume is that the graph is given by

Â its adjacency list.

Â The graph is going to be given by its adjacency list, not adjacency matrix.

Â The second thing I'm going to assume,

Â without loss of generality, that this, the, the graph that the,

Â the algorithm is going to run on is going to be connected, okay?

Â The, the graph is going to be connected, which means there is a path from i,

Â the initial node, to every other node in the graph.

Â 1:29

And the third thing we need to talk about is what is the input size okay.

Â When we talk about adjacent sorest, it makes sense to,

Â to think about the number of nodes and the number of edges.

Â So I will assume that I have N nodes and M edges.

Â Okay, so the number of nodes is N and the number of edges is M.

Â Now that we know that the input size parameters are m and n,.

Â We know it is represented as an adjacency list,

Â I assume it is connected, let's see now how long it takes.

Â Okay, so now, the first line is initialize q on m t q,

Â this is, again, a basic operand individual operation,

Â a basic operation that we will assume it takes on the order of one step, okay.

Â So, I will say on the order of one step.

Â Remember that all one basically says that it takes a constant number of operations.

Â 2:47

Enqueue Q, i, adding an element to the queue is also a constant

Â number of operations, it is 1, or a constant amount, a fixed amount of time.

Â Now we come to this loop here.

Â Now, how many times is this loop going to iterate, while Q is not empty?

Â Do the following.

Â Now if you, if you think again about the illustration we showed.

Â We had a graph with six nodes, and we illustrate this, this algorithm on it.

Â If you go back and look at the illustration, you will

Â notice the first thing you will notice that each and every node in the graph.

Â Was added once to the queue.

Â We started by putting node zero onto to the queue and then we put the neighbors of

Â zero on the queue, and then the neighbors of the neighbors and so on.

Â So if you think about the algorithm carefully, every node.

Â Is going to be added to the queue.

Â Remember I made the assumption that the graph is connected,

Â and this is where that assumption comes into the play and allows me to

Â make that statement that every node is going to be added once to the queue.

Â Because remember,

Â if the graph is not connected, some nodes are not going to be added to the queue.

Â 4:18

In every iteration, what happens to that q?

Â In every iteration, the first line in that iteration is d q,

Â so in every iteration, we are also going to remove a node from that q.

Â So the q is going to have n elements added to it.

Â In every iteration, one node is going to be removed from the queue.

Â Okay, so if you think about these two statements,

Â that every node is going to be added once and every iteration at least, and

Â every iteration exactly one node is going to be removed, this,

Â these two statements combined tell us that this loop is going to iterate n times.

Â Okay, it's going to take n times.

Â So this.

Â While loop here.

Â 5:01

Again just to make sure you understand the concept if, if we still have

Â the first statement that every node is added exactly once on to the queue, but

Â in some iterations, none of the elements on the queue are removed.

Â Then I cannot make this statement because if in certain iterations nothing is

Â removed from the queue, then I will have more iterations and if you don't remove,

Â if you don't have this line here,

Â if you just look at the value of j without removing it from the queue,

Â this actually will turn the algorithm into a non-terminating algorithm, okay?

Â So again, you have to reason carefully about.

Â What's happening to the Q to be able to understand,

Â how may times is this loop going to iterate?

Â Every node is added exactly once, and

Â every iteration, exactly one node is removed.

Â Therefore we have n iterations.

Â 5:57

For each neighbor h of j do, how many neighbors can, can j have okay?

Â In the worst case for

Â some, for some nodes we might have n minus one, at most n minus one.

Â Of course, we have, when we are talking about an adjacency list.

Â There is a given number of neighbors for every node.

Â But again, as we said, we are not trying to get at the exact number of steps here.

Â We are going to get an approximation.

Â So I can approximate things and say this loop, this this line here, for

Â a node j, I can have, at most, in minus one neighbors.

Â Okay?

Â In a graph that has n nodes, every node has, at most.

Â N minus one neighbors.

Â so this one here I can say it's all of N, okay?

Â Because N minus one is all of N.

Â This statement here, the if statement is, is a simple, condition to test.

Â It's just a fixed amount of time.

Â This is simple assignment here is, fixed amount of time,

Â that adding something to the Q is also fixed amount of time.

Â The return is o of 1, okay?

Â So now that we have these numbers for

Â every line, how long does this algorithm take, okay?

Â So we have o of 1 here.

Â [NOISE] Then we have this loop here is going to take.

Â O(n).

Â This one, this line here is going to take O(1).

Â These two, combined, they are going to take O(1), okay?

Â Now, we have this big one here, okay?

Â How long is going to take?

Â This is going to iterate n times, n times, and in each iteration,

Â we are going to be doing also n times plus sum constant.

Â So, we know now that this is going to be on the order of n squared.

Â Okay? So these constants can go away,

Â this constant, these constants and so on.

Â So it's order of n times order of n is going to give me order of n squared.

Â And this line here, is just 0(1).

Â So now I can just sum these numbers,

Â I say its 0(1) plus 0(n) plus 0(1) plus 0(n) squared plus 0(n), 0(1).

Â This is going to give me that the algorithm takes.

Â [SOUND] Again it's O of n plus O plus n squared but,

Â we focus on the dominating terms.

Â n squared is a dominating one here.

Â So, [COUGH] by using this analysis we get that algorithm, is O of n squared.

Â So this is our first attempt at analyzing the efficiency of this algorithm, and

Â as you can see this is a very efficient algorithm.

Â It takes quadratic amount of time in the, in the number of notes in the graph.

Â So like before when we focused on when we looked at Brute force algorithm.

Â For computing distances, remember that even for, for 250 naughts or

Â something like that the algorithm would have taken ten to the 59 years.

Â If you have 250 naughts and it's going to perform in the order of

Â 250 squared this is going to be done in fractions of a second.

Â In, in, in today's computers okay.

Â So this is a very efficient algorithm.

Â And this is using our first attempt at analyzing running

Â time that we get an O events squared time, so

Â we can say that bvs takes a quadratic time in the number of nodes

Â