0:00

Okay, so, last time, we, we basically looked at the brute force algorithm for

Â computing distances.

Â And for each line in the, in the algorithm,

Â we basically wrote next to it the number of operations it's going to perform or

Â the number of iterations it's going to perform.

Â Because for loops, for

Â example, we need to talk about how many times they need to, to iterate.

Â For other lines, how many operations each take?

Â Now the question is, what does this add up to?

Â Okay? Because at the end of the day what we

Â want to understand is how long does the algorithm take, and how bad is this?

Â Or how good is this?

Â Because if I add up this and it it's going to tell me

Â that there are going to be five operations only, that's a good algorithm.

Â If I add up this, and it tells me that for just ten nodes,

Â it's going to perform over 10 million operations, then I need to think seriously

Â before I implement this algorithm, because it wouldn't seem feasible.

Â So what do these things add up to?

Â It's not it's not a hard exercise, but

Â we have to be careful about how we add up numbers.

Â Because this, these iterations here in particular, one, two, three.

Â They have k minus 1 in them.

Â Or the variable k.

Â And k is the variable that is going to go from one to n minus one.

Â So, we have to be careful about how we add them.

Â Of course we can do handwaving and put upper bounds and

Â start doing some rough calculations.

Â But that might actually take us very far from the actual running time.

Â So, for once I'm going to try to do a careful summation of these,

Â of these numbers operations to try to get at what kind of formula we get in

Â terms of n, because remember, I can not give a formula in terms of k.

Â K is not part of the input size.

Â Okay? My formula has to be a function of n and

Â m or, either n or m or both of them.

Â M is not showing anywhere here.

Â We have to, to think about it as in terms of, of n here.

Â 1:56

Okay?

Â So let's start here.

Â The, one of the easiest thing to think about is that this one here,

Â this operation is outside this loop.

Â And this operation outside this loop.

Â So, lines 1 and 14 are outside the loop, and they going to,

Â each one of them's going to be performed once when the algorithm is run.

Â So line 1 and 14 contribute 2 together.

Â 2:34

Inside this loop we have this line 3, line 4 and

Â line 13 are going to execute ones each.

Â Okay?

Â For every iteration of this wide loop, we're going to do one, two, three.

Â One, two, three, and so one.

Â This loop is going to iterate in minus one times so

Â we have plus three times n minus 1, okay?

Â 2:58

Now, we come to these loops.

Â Now, even though this loop is wrap with this while,

Â we can forget about the while, we don't have to multiply n minus 1 by this.

Â But we can think about this in terms of the k.

Â So the first time we come, we enter this loop,

Â k is going to be 1, and it's going to look at every subset of size zero.

Â The second time is going to look at, the second time

Â 3:24

we come through this loop it's going to be looking at every subset of size one.

Â The third time is going to be looking at every sub-set of size three, and so on.

Â So, in this case here, we can say that now we have,

Â as k goes from 1, k goes from 1 to n minus 1.

Â We write this, and we have to sum, the number of operations it's going to take.

Â So we have a summation, from k equal 1, to n minus 1.

Â This symbol here, Big Sigma,

Â from k equal 1 to n minus 1 says that we are going to take the summation,

Â of some term, that has, that is a function of k, from k equal 1 to n minus 1.

Â Summation of what?

Â 4:53

Okay? So how much work is here?

Â We have one is going to be performed.

Â This is one.

Â We have two.

Â This is line 7 is going to be performed once.

Â Line 11 is going to be performed once.

Â Notice that since we are looking at worst case scenario,

Â we are never going to hit equal true.

Â This is, this, this condition here will never evaluate the truth, so

Â you will never perform this.

Â So we'll have one and two.

Â They will always be performed.

Â Times 2, plus so we have two here.

Â Plus this loop here is going to perform from zero to k minus 1 which is k times,

Â k times, we will perform this and this.

Â Okay? So, for

Â k times, we are going to check, if it is not an edge.

Â Takes 1 operation.

Â We are going to assign, assign force to it, okay?

Â So here, plus 2k.

Â 5:48

And this is the running time, okay?

Â So here, if I sum up all these, I will get this formula for

Â the running time here okay?

Â So it's 2 plus 3 times n minus 1, plus k equal 1,

Â for, sum from k equal 1 to n minus 1 of this.

Â Okay?

Â So now we get to this running time of the algorithm, how bad is this running time?

Â Okay?

Â Of course, one way to think about this is to use some tool that will allow us to

Â compute this.

Â So you can actually write the Python program,

Â a simple Python program that when will evaluate this term.

Â And you can give it, you can give it different values of n and, and see how,

Â how it grows.

Â In fact, actually, I tried it.

Â And if you give this this function n equal 2, for example,

Â 7:02

So, notice this.

Â I almost doubled the input size.

Â I almost doubled the input size.

Â The running time or

Â the number of operations group by an order of magnitude okay?

Â So it went from 13 to 500.

Â Once I doubled this the number of operations did not double,

Â it actually it grew, it grew much faster than that.

Â Okay?

Â Now if I take n equals 10 [SOUND] this formula here,

Â it evaluates to a number that is actually greater than 13 million.

Â Okay?

Â 7:36

So notice again what's happening.

Â I take I take a graph of size 2.

Â The algorithm is going to perform an order of 13 operations.

Â I take, I double the size of the, of the graph.

Â I go to five.

Â The, the algorithm performs over 500 operations.

Â I took this and doubled it.

Â I just went from five nodes to ten nodes.

Â It's taken now over 13 million operations.

Â 8:03

Now, imagine now what would happen if I double it now.

Â From n equal 10 to 20.

Â If you look at this kind of growth,

Â they're going from 13 to 500 to 13 million.

Â You can imagine if I double n, now all of a sudden the number is going to be huge.

Â Okay?

Â Much, much larger than 13 million.

Â What does that tell me?

Â First thing it tells me about this algorithm is that you know,

Â it's take 13 million operations on a graph of size 10.

Â Remember, what was or original motivation for this problem of computing distances.

Â We wanted to look at that problem of, is the world small and

Â trying to quantify whether we have a small world effect in a given network.

Â And we said for example, our input network can be the Facebook network.

Â Facebook network today, if we want to get all the data on the Facebook network.

Â It is estimated to have over a billion nodes, billion nodes okay?

Â We are talking about n equals 10 nodes that has taken over 13 million operations

Â now, imagine what would happen with this sort of growth from 13 to 500

Â to 13 million what would happen if i replaced n equals 10 by 10 billion.

Â 9:12

Okay? Now, even if we don't analyze all of

Â Facebook, even if I just sample 1000 nodes, okay,

Â just take 1000 accounts of Facebook and analyze, now replace n by 1000.

Â And you will get basically a number, that no matter how fast the computer is,

Â we will never be able to analyze it using this algorithm.

Â Okay? So I repeat,

Â that it's not just about the operations.

Â It's going to grow to a point that no matter how fast the algorithm is, even

Â the computer is, even if it can perform 1 billion or 10 billion operations a second,

Â it's not going to be able to handle a graph with even thousand nodes in it.

Â Okay?

Â 9:51

Now, the second point I would like to make here is that if you look at

Â this kind of analysis,

Â you can immediately see with this type of formulation here that it is tedious.

Â It is tedious because we have to look at every, at every line and

Â count operations and do careful summation and so on.

Â Now does this matter?

Â Does this equation matter?

Â Or does it, what matters to me is that when I look at these numbers I'm

Â seeing that the function is growing very fast.

Â Okay?

Â Now if I look at this algorithm from a different angle.

Â I say, okay let's think about roughly about what is this algorithm doing?

Â Notice that in the worse case,

Â this algorithm if going to be looking at every sub-set.

Â It's going to be looking at every sub-set size of zero, one, two, three,

Â four, five, all the way to, to n.

Â Right? To n minus one.

Â So, what is the, what is the number of sub-set of a set of size n minus 1?

Â It is 2 to the n minus 1.

Â 10:46

Of course, this algorithm is doing much more than this.

Â But all I can say is that this,

Â the running time of this algorithm has a lower bound of 2 to the n minus 1.

Â And this is what we call an exponential function that grows very fast.

Â As n grows if you double n, the running time is going to grow exponentially.

Â It does not grow linearly, for example.

Â Okay?

Â So, the only we can say that this, this algorithm.

Â I can do much more hand waving and avoid this and say, I can bound this one,

Â the running time of this algorithm from below by 2 to the n minus 1.

Â This is sufficient to tell me this is a bad algorithm because it's

Â going to take at least exponential amount of time which grows very fast.

Â As n reaches thousand.

Â As I said, you know, if I want to analyze a Facebook network with thousand nodes,

Â 2 to the 1000 or 2 to the 999,

Â this is not a number of operation that today's computers can deal with and

Â probably not the computers in ten years that can deal with, okay?

Â So, we can do this kind of analysis, but

Â we can start thinking about the growth of functions, and start to think about,

Â instead of this exact term, I can start thinking about lower and

Â upper bounds to understand roughly what is the running time of this algorithm

Â