0:00

Okay. So now,

Â that we have talked about what we mean by efficiency and

Â that we will focus on time as a metric for efficiency how long an algorithm takes.

Â The next question is how do we measure efficiency?

Â How do we measure the amount of time an algorithm takes?

Â Again I remind you, that we are not talking about how much time,

Â this specific Python implementation of an algorithm takes.

Â We are talking about the algorithm given in pseudocode,

Â just still in theoretical terms, how long does that algorithm take?

Â Of course, we are not going to go into the number of seconds and number of hours, and

Â so on, about the algorithm, because that's not doable.

Â That, in order to know how many, how many seconds or

Â how many minutes an algorithm is going to take,

Â it has to be implemented, it has to be run on a specific machine, and so on.

Â So then, we have lots of issues that are beyond our control, and

Â beyond the specifications of an algorithm.

Â If I ask, how, how many minutes does an algorithm take,

Â then I'm talking about the specific implementation on a specific machine.

Â Once you change the computer or change the machine that you are running the algorithm

Â on, or the implementation on, then it's going to, the time is going to change.

Â So, we are not interested in that type of analysis at this point.

Â We are asking a question that this algorithm that we have developed, or

Â any algorithm we see, if we take an algorithm from a textbook, how much time,

Â roughly, how much time does it take?

Â So, the question is, what do we mean by that?

Â And when, the, the most important thing, or

Â the most crucial thing to know about running time efficiency.

Â And how we measure it,

Â is that it is all a function of the input size, the input size.

Â So, if I look at that algorithm and I take a certain input to that algorithm, and I

Â measure the size of that input, then I ask how many operations, how many operations

Â is that algorithm going to, they going to perform as a function of that size?

Â So if the size of the input is five,

Â whatever five means, what is the running time?

Â How many, how many operations is the algorithm going to execute?

Â Is going to execute five.

Â Which is equal, equal to the number to the, to the size of input.

Â Is it going to execute 25, which is 5 squared, or

Â is it going to execute 32, which is two to the five operations, for example.

Â So, it's all a function of the input size.

Â How much time or how many operations is the algorithm going to

Â perform as a function of the size of that input.

Â Now, what is the size of an input.

Â Now that's not the, that's not the simplest concept to introduce here.

Â But we will think about it in classes of algorithms, okay?

Â So I will think about it,

Â for example, what is the size of an input of an algorithm that deals with grass?

Â Or that deals with, with lists, or that deals with strings, or

Â that deals with numbers?

Â Okay. So,

Â we will see lots of algorithms in this course that deal with graphs.

Â The input is a graph, or two graphs, or ten graphs and so on.

Â What is the size of a graph?

Â 3:05

in that graph, or the number of edges in that graph, or both.

Â So, if we write an algorithm, for example, that takes as input a graph,

Â an undirected graph, and computes all pairwise distances,

Â the distance between every pair of nodes in it.

Â Well, then I ask what is the input size of the graph?

Â I count the number of nodes in it.

Â I count the number of edges in it.

Â And I use these two parameters as the input size.

Â So, it might have N nodes and M edges.

Â N and M are the parameters that denote the input size.

Â Then, when I say, what is the running time of this algorithm,

Â I would like to get to a function of N and M.

Â So, I might say that the running time of the algorithm is N squared.

Â It takes time, it takes time that his proportional to N squared.

Â What that means, is that if you have ten nodes the algorithm is going to,

Â to, to perform on the order of 10 squared or 100 operations.

Â If you have 1,000 nodes, it will perform on the order of million operations.

Â It can be also that the running time is N plus M, for example.

Â Then, if you have ten nodes and, and

Â five edges, it's going to perform in the order of 10 plus 5 operations.

Â Okay?

Â So, we need to determine the size of the input.

Â Again, in the case of graphs, the number of nodes, the number of edges, or both.

Â And then we need to think about the number of operations that algorithm performs,

Â as a function of N and M.

Â This is how we measure running time.

Â It's a function, we need to get a function of the size of input.

Â In the case of graphs, a function of N, or a function of M, or a function of N and

Â M combined.

Â 4:46

If we think about sorting and searching algorithms, okay?

Â So, these are some of the traditional algorithms that are covered basically in

Â every classic algorithms textbook.

Â An algorithm for sorting, if I give you a list of numbers n numbers for

Â example, and I want to sort them in ascending order, in descending order.

Â You know, when we grade and the, the exams in the course,

Â we usually sort the, the grades in descending order.

Â We want to see what is the highest grade in the course,

Â what is the lowest grade in the course?

Â So that we get an idea about the performance.

Â How do we sort a list of a, of a grades, for example?

Â Now, we are not now talking about that algorithm.

Â But if I have an algorithm that sorts a list of numbers,

Â of n numbers, what is the input size here?

Â It is, it is accepted that the input size for sorting algorithms or

Â searching algorithms.

Â For example, I have a list of n names and I'm going to search for a specific name.

Â The input size in this case is, is the length of this list.

Â Or how many elements are in that list.

Â So if I'm sorting a list of 100 integers, then the size of the input here is 100.

Â Or more generally is that, if we have a sorting algorithm that works on a list, or

Â a searching algorithm that works on a list,

Â the input size is usually the length of that list.

Â 6:06

We will see algorithms that work on strings.

Â Okay? So, some lists or

Â sequences of, of alphabet symbols.

Â So, for example, I will have certain text, and I'm going to be looking, searching for

Â certain text in it.

Â Okay?

Â So, I have the, the text that corresponds to a book for example, and

Â I say, find all the instance of the words school in that text.

Â Okay.

Â So the input there is a very long strain that corresponds to all the texts.

Â And the algorithm is going to perform some operations to find the number of

Â instances that the world's school appears there.

Â What is the, what is the input size in this case?

Â When we have an algorithm that operates on string,

Â usually the input size is the number of characters in that string.

Â So if I have the word school for example, there is S-C-H-O-O-L.

Â The input size is six, I have six characters, okay?

Â And so on.

Â 7:35

Now, we say that if you're sorting a list of N numbers,

Â then the size of the input is N.

Â So here, one can look at this and

Â say this is a list of one number in some sense, so the size of the input is one.

Â However this is not accurate in this case.

Â When we look at this kind of algorithms that look at number and try to find for

Â example, the factor of that number or the, we, w, check if the, if the number is

Â prime, then the input size here, is the number of bits that are needed.

Â To represent this number, okay?

Â So it's usually because in,

Â in computer science we focus mainly on zero one representation.

Â Or the presentation of a number in the binary, on a binary scale.

Â Usually the number of bits needed for

Â representing p is the log of the value of P to the base two.

Â 8:48

Now it is, when we talk about, about running time efficiency,

Â as I say it is all a function of the input.

Â But then okay,

Â if I specify the input size, and I say it is N and M, then what do we do?

Â Once you specify the input size and

Â say that there are N nodes in the graph, M nodes, edges in the graph.

Â Then it is all about counting operations.

Â How may operations is the algorithm going to perform?

Â Okay?

Â So here, we have to make lots of assumptions and

Â we do make these assumptions when we, when we analyze running times of algorithms.

Â And the, one of the the the major assumption we make is that.

Â All individual operations in the algorithm, like comparison of values,

Â like multiplication of two numbers, addition of two numbers,

Â division of two numbers, indexing into an array.

Â If I have an array I say what is the element at position seven in the array.

Â All these kind of operations or calling a function, or

Â returning from a value to a function.

Â All these kind of operations, each one of them, we will assume that it

Â takes fixed amount of time, that is independent of the input size, okay?

Â Of course, this is not the, the, the assumption that is really, practical.

Â Or, or, if does not reflect what happens in practice,

Â because division of two numbers that have, that have million bits in them

Â is going to take much longer time than the addition of such two numbers.

Â But, here we are trying, not trying to get the exact number of operations that the,

Â the, the algorithm is going to perform.

Â We are trying to get an approximation of that number.

Â Okay?

Â So the major assumption we are going to make is that, every operation,

Â every individual operation, like multiplication, addition, and so

Â on is going to fixed amount of time that has nothing to with the input size.

Â 10:41

Okay? Now, we will focus,

Â when we talk about the performance of an algorithm, one of the,

Â the crucial things to, to state up front is.

Â Under what scenario are we analyzing running time?

Â There are three possible scenarios for analyzing running time.

Â There is worst case.

Â In the worst case, how long is the algorithm going to take?

Â There is the best case, which is in the best case,

Â how long is the algorithm going to take?

Â And there's an average case, on average, how long is going to take for

Â the algorithm?

Â Now, the question is what do we mean by worst case?

Â What do we mean by best case?

Â What do we mean by average case?

Â In this course we will mainly forecast on worst case analysis.

Â And what do we mean by worst case analysis?

Â 11:24

When we talk about the, the running time as a function of input size, and

Â I say the input size is, the graph has N nodes and M edges.

Â When we talk about worst case analysis this is what we mean.

Â Of all graphs, of all graphs that have N nodes and M edges, which

Â one of these graphs, causes the algorithm to take the largest amount of time?

Â Again of all graphs that have N nodes and

Â M edges, which one causes the algorithm to take the longest amount of time?

Â This will be the worst case analysis.

Â Notice that we fix the, the input size, and for

Â that fixed input side we ask, which input of that side is going to

Â cause the algorithm to take the longest amount of time?

Â We never ask what is the largest size of an input,

Â that is going to cause the algorithm to take the longest amount of time.

Â That is actually a useless question in some sense, because just keep increasing

Â the input size you keep increasing the running time of that algorithm.

Â