0:00

Okay, so now that we talked about efficiency, and

Â we said that we're going to focus on efficiency in terms of time.

Â We talked about as, as a function of the input size.

Â We talked about it as a, as measuring the number of operations.

Â We talked about it as a, as a analysis under worst case scenario.

Â We are going to go back to the, to the starting point that,

Â that actually launched us into this discussion about efficiency.

Â Which is the brute force algorithm for

Â computing the distance between two given nodes, I and G.

Â Remember that our problem was, given as input, an undirected graph G, and

Â two specific nodes in the graph, I and G, we wanted to compute the distance.

Â Now we want to analyze the running time.

Â We want to get an estimate of the number of operations that,

Â that algorithms performs, okay?

Â So, here on the board, we have that algorithm.

Â I'm not showing the name of the algorithm, or the input and output.

Â Remember the, the algorithm is brute force distance.

Â The input is a graph G, and two nodes in it, I and G.

Â And the output is the distance, DIJ.

Â 1:03

This is the algorithm that, that we, we, we gave before.

Â It has all these details.

Â The first question we need to ask,

Â again when we analyze the running time of the algorithm, is, what is the input size?

Â As I said, when we deal with graphs and graph algorithms, it is, it makes sense to

Â assume that input size is the number of nodes, and the number of edges.

Â So the first thing I'm going to assume is that the graph has N nodes and M edges.

Â Okay?

Â So, the graph has N nodes,

Â N nodes and M edges.

Â 1:42

The second thing as we said, we have to make,

Â we have to talk now about specific implementation.

Â And as I said, that means we have to talk about implementation details, or

Â how, what, what kind of assumptions are we making about this algorithm?

Â Now notice that for this algorithm, you know?

Â Most of it is, is clear, you know, I don't need to talk about, or

Â think, reason to much about this assignment.

Â Because I'm assigning the value 1 to K or returning infinity and so on.

Â One of the assumptions I have to make is about how is the graph represented.

Â Okay?

Â And in this case, I'm going to

Â assume that the graph is represented

Â as an adjacency matrix [SOUND] okay?

Â Everything else is probably clear here.

Â And then the third question again is that under what scenario are you

Â going to analyze.

Â As I said before we're going to focus mainly on worst-case scenario.

Â So the first question is,

Â what's the worst-case scenario in the case of this algorithm?

Â Or, of all graphs of size N and M, N nodes and M edges.

Â Which graph is going to force this algorithm to run

Â the maximum amount of time?

Â This is the main question.

Â Now, notice that this algorithm is doing certain loops here.

Â It's going to look at every subset of K minus1 nodes.

Â It's going to look at every permutations or arrangements of these K minus 1 nodes.

Â It's going to keep doing this while incrementing K from 1 to

Â n minus 1 as we said last time, where N is then size of V or the number of nodes.

Â So, what would force this algorithm to perform all the, all the alteration here.

Â Which means, all N minus 1 alterations,

Â what will force it to look at every possible subset.

Â What will force it to look at every possible permutation.

Â 3:44

If you think about it carefully, the answer is, when I and

Â G, the input nodes have no path between them.

Â Okay?

Â Because if I and J are neighbors, for example, if I and

Â J are neighbors, then this algorithm, when it starts, it's going to say K, K equal 1.

Â It's going to look at all subsets first of size zero, which basically means nothing.

Â It's going to check if there's an edge I and J.

Â Since they are neighbors, it's going to find it.

Â And is going to get to this point if IsPath is true, it's going to return K.

Â So, all that algorithm is going to do, do one iteration here, and

Â one iteration here, and one iteration here, and it's going to finish.

Â So, is less going to actually be the best case.

Â If I and G are neighbor that's the best case for their algorithm.

Â But, how do I force it to look at every possible subset of

Â every possible size between one and, and minus one.

Â And every possible permutation.

Â Again if there is no path between I and J it means there is no path of length one,

Â no path of length two, or three, or four, or five, or N minus 1.

Â So it's going to be doing all of this.

Â So worst case scenario [SOUND] I and

Â J the two input nodes, are not connected.

Â Or, in other words, there is no path between them.

Â 5:15

There is no path between them.

Â Okay? So, now that we have answered these

Â three questions, what is the input size?

Â What do we mean by the representation, the specific rep the specific implementation?

Â And what kind of, of case we are looking at.

Â Now we can move on and start counting operations here.

Â Okay, we can start counting operations.

Â And at the end get some sort of function in terms of N and M.

Â Again it might just be a function of, terms of N or M or both.

Â Okay?

Â So, now that I have answered these I'm going to erase this, and

Â we are going to start analyzing the running time of this.

Â And looking at each one of these lines and deciding on the how many steps or

Â how many operations, the algorithm is going to take.

Â 5:57

Okay, so the first thing we need to do is number the lines and

Â spe, talk about specific lines.

Â [SOUND]

Â Okay.

Â So, we come, the first thing we can do is first focus on the simplest lines, okay?

Â As I said, when we do learning time analysis we make that

Â big assumption that all, all individual operations.

Â Take fixed amount of time regardless of the size of the input.

Â So if I look at individual operations here for example, assignment eh,

Â comparison is K smaller than, than the size of the, these assignments.

Â This assignment here, this assignment and so on.

Â These are all, each one if them take one operation.

Â So, I can now start thinking about the numbe,

Â counting the number of operations here.

Â [SOUND] How many operations does this line take?

Â It takes one.

Â I'm assuming it takes one operation regardless of fixed amount of

Â time regardless of input size.

Â What do I mean by a fixed amount of time?

Â I'm going to count it as one.

Â Okay?

Â This line three here, line three is going to take also fixed amount of time.

Â I'm going to label it as one.

Â This line here is just one individual operation, one, one step.

Â This line, its path taking through, is going to take one.

Â This if statement here, I'm checking if this if this

Â edge is not in E, I will assume that it takes one operation here.

Â [SOUND] Is path takes false,

Â I'm assuming it takes one operation, okay?

Â And IsPath True, I'm going to ta, assume it takes one operation.

Â And return K is one operation, K plus 1 is one operation.

Â We need to adjust the numbers here, this is 13.

Â It's one operation.

Â And this is 14, one operation.

Â Okay?

Â Just to make sure

Â we can label [SOUND] okay?

Â So, we have 14 lines in the algorithm.

Â We started with the simplest ones.

Â Again, assignment, assignment here, assignment we are asking if it, it equal,

Â we're checking equality assignment, assignment, return and so on, okay?

Â So we're looking at these ones, actually we can be a bit more details.

Â Here it's not just assignment, we're adding a number and then assigning it.

Â So, we can say it is 2 here, and so on, okay?

Â But you know, in the, when we do the analysis,

Â we'll notice that one versus two is not going to make a difference.

Â Okay? Now we start looking at the other ones.

Â Okay? So we have a while loop here.

Â It's going to loop again, K starts at one, and it's at the size of V.

Â Remember, the input size is N and M, it has N nodes.

Â So this is going to be n, okay.

Â The size of V is N,

Â and K is going to go from 1 all the way to the last number before N.

Â So it's going to go to N minus 1.

Â So, K is going to take values 1, 2, 3, 4, until N minus 1.

Â So this is going to loop here or iterate N minus 1 times.

Â Okay?

Â 9:42

Now we come to these two, we have two, these two lines here,

Â and we have this one.

Â This one is easier, is simpler.

Â For L equals 0 to K minus 1.

Â How many times in this loop going to iterate?

Â L equal to k minus 1.

Â 0, 1, 2, 3, 4, until K minus 1.

Â That's K times.

Â This is going to iterate K times.

Â Okay?

Â This iterates K times.

Â Then we have these last two here.

Â And here, now we have to make use of some mathematical results without proving them.

Â 11:33

The second one is that the number of permutation of a set size K

Â is K factorial, okay?

Â >> Or, I can say here that,

Â if I have a number of permutations

Â of a list of N elements is

Â N factorial, okay?

Â So, we need these two facts that the number of permutations of

Â a list of N elements is n factorial and if I have a set of size N and

Â I'm choosing subsets of size K, there is N choose K,

Â which is N factorial divided by N minus K factorial divided by K factorial.

Â Why are these needed?

Â Because we are looking at subsets and permutations.

Â So, here for each subset V prime of size K minus 1, okay?

Â So, we're looking at subsets of size k minus 1 of set V, which has N.

Â So, how many possibilities are there?

Â If I have a set of N elements.

Â And I need to look at subsets of size K minus 1.

Â How many possibilities are there?

Â Using this result here, this is going to loop or iterate

Â 13:34

We have many lines that are going to take single operations,

Â then we have this loop that's going to iterate N minus 1 times,

Â we have this loop that takes N, choose K minus 1.

Â This loop is going to take K minus one factorial,

Â this is going to take on the order of K times, this loop, and so on.

Â And this is what we do with the running time analysis.

Â We get these number of operations.

Â Now, what we do is we start adding these up because the running time of

Â the algorithm is going to be the addition of this, okay?

Â Now, I'm not going to add them up here,

Â because we are going to have to take care actually of all these loops, and

Â how they are nested, so this K, for example, is, is a variable.

Â It's going to be, it's going to be changing from, from one to N minus 1, and

Â so on, okay?

Â But later we are going to get to a point where I am going to write down that

Â what is the running time of this algorithm.

Â But here I counted the number of operations.

Â Now if I put these numbers correctly in, in the formula and

Â I just add, add them correctly I'm going to get that formula of

Â the running time as a function of the input size.

Â So everything here, if you look at it, it's a function of N.

Â And nothing else, because this K, this K minus 1, are going to go,

Â are going to go away, once we notice that K is going to loop from one to N minus 1.

Â