0:00

Okay, so now we have done binary search, and we have seen how it works.

Â And it takes the list, divided in two halves, decides on which half to go to.

Â It comes here and divide and decide which half, and so on.

Â Until it gets to an item, to a list of one item and

Â then checks, is that the item I'm looking for?

Â If not, it just returns minus 1.

Â If yes, it returns the, the index of that item and done.

Â So what is the running time of this algorithm, okay?

Â It is a recursive.

Â We will have a recursive implementation of it.

Â It is divide and conquer.

Â And let's think about it the similar way that we thought about about So

Â I'm looking at the running time of this T of n.

Â And I'm saying, how long does binary source take on a list of size n?

Â Okay.

Â So what did, what did binary search do?

Â It divided the list into two halves.

Â Each of size n over 2.

Â Remember that this was.

Â This number here is the number of, of sub problems.

Â And n over 2 is the size of each sub problem.

Â It divided into two halves.

Â How many of them did we solve?

Â So when I call binary search again, I am not calling it on this and this.

Â Actually, when I divide it into two halves, as I said this we kill this

Â branch, because I know I'm not, I don't the element is not going to be here.

Â So I don't solve in merger sort it was 2 times t over n over 2,

Â because I know that to solve the left half, I need to solve the right half.

Â In binary search, once you decide it's not in the left half you ignore it.

Â Therefore, and you just go on the right half.

Â Therefore it is 1 times t of n over 2.

Â So we, we divide it into 2 sub problems, or 2 less each of size n over 2.

Â We solve one of them, we solve one of them.

Â And then, see, how long does it take to do the merge?

Â Merge in fact, it's why we don't do any merge, and it is O of 1.

Â Okay?

Â It is O of 1.

Â For the base case T of 1 is O of 1 as well, right?

Â In the case of this one last you are just doing the comparison.

Â 3:49

And, it should make sense because, this, algorithm is going to divide,

Â look at this half, divide, look at this half, divide, look at this half.

Â So, really, the amount, the amount of work that it's doing is best than this,

Â than this, than this, so I'm going one call, one call, one call, one call.

Â So, it's basically the height of this tree, going from here to here, so

Â it's just one path.

Â That is going to take.

Â What is the height of this tree?

Â If you think about it carefully, because I take this divided it into two.

Â This into two.

Â This into two.

Â Where do I stop?

Â If this had n, you will notice that you will have to

Â stop after log of n of course it's base 2.

Â So, the height of this tree is going to be all of log n.

Â And this is why, this algorithm is actually going to take log n.

Â So this is the intuitive explanation,

Â that the height that it's going to take is log n.

Â And the same thing here, the master theorem, without thinking too much,

Â it will have given me exactly the same thing, O of log n.

Â 5:00

And linear search, of n.

Â So, does this mean that, every time I have search,

Â I always run binary search, because log n is better?

Â The answer is no because, remember that there's a big

Â assumption about binary search, that the list has to be sorted.

Â If it is not sorted, this is not going to work.

Â If it is not sorted, this will work.

Â This works on anything.

Â Whether it is sorted or not sorted, this will work, okay?

Â And the worst case is we will take O of n, regardless of it is sorted or not.

Â This one is going to take in the worst case of login.

Â So, when you have a list and an item, and

Â you're searching for them, Yyu do a binary search or a linear search.

Â [COUGH] If it is not if it's not sorted,

Â you can either do O a linear search or you can sort and do binary search, okay?

Â So.

Â I can do linear search.

Â 6:00

I can do linear search, which will

Â take O of n or, I can do sort, first,

Â and then I can do binary search.

Â But, this is going to take, we have seen it already,

Â n log n, plus O of log n, and this is of course O of n log n.

Â So it doesn't make any sense to sort, and do binary search.

Â Just do linear search, and you are going to get the O of n.

Â So would we ever sort, and do binary search over this?

Â The answer is no.

Â If all you need to do is just one search operation, if,

Â if all you care about is just one-time search, you should do this.

Â If all you care about is twice, three times, four times,

Â seven times, a small number of searches, do this.

Â But, imagine what would happen if you have a list with, with millions of items, and

Â your search operation is done millions of times.

Â Then it is worth putting the effort into searching first, and

Â then start doing all the other search queries in log n, okay?

Â So, this is a very important algorithmic principle here.

Â That sometimes, it is worth pre-processing the data,

Â before we start doing the actual operations we're interested in.

Â The pre-processing here was sorting, so that I can do the search efficiently.

Â It is, this is worth it when n log n is not going to be the main factor.

Â N log n is not the main factor.

Â It is when the number of operations here, actually overwhelms this.

Â So I will always have n log n for the sorting, plus k

Â times log n, where k is the number of search queries that I will be executing.

Â If k is much larger than n, this is worth it.

Â If k is too small this is not worth it.

Â Okay.

Â So this here,

Â now that we have seen sort, you can start using sort as a pre-processing technique,

Â pre-process the data and do the other operations much, much faster.

Â This belongs in some sense to the category of transform and conquer.

Â This kind of approach in the sense that I wanted to do a search on a list,

Â I transform the instance of the problem by sorting it,

Â and then I did my actual solution to the problem, okay.

Â So keep in mind that sorting while it is about getting a sorted list of items.

Â Sometimes we, it is a very powerful technique for pre-processing the data, so

Â that subsequent operations, whether they are searching or comparison, and

Â so on, can be done very efficiently.

Â Okay?

Â There are many operations, that if you do them on an unsorted list are going to be

Â very unefficient, inefficient.

Â And these operations, once you have preprocessed the data so

Â that it is sorted, they become efficient all of a sudden.

Â So it's very important to keep in mind that, if you are doing just one search

Â operation, or five, or 100, or, or 1,000, it is not worth going through this.

Â Do linear search.

Â If the number of queries is, is, growing all the time, and

Â it is a very large number.

Â It is worth pre processing the data so

Â that every time you do the query, it is taken a short amount of time, okay.

Â So in this set of lectures we have seen divide and conquer technique, for

Â merge sort, for binary source, how we divide a big problem into sub problems.

Â Then solve each one of them, and then merge the results.

Â Remember that there are three steps.

Â We have seen that,

Â the natural implementation of these algorithms is recursive, where you

Â call the functions multiple times on the, in the instances of the sub problems.

Â We saw that these recursive algorithms naturally give rise,

Â to formulas that we call recurrences for the running time of the algorithms.

Â We have seen how recurrences of this specific form can be solved using

Â the master theorem, to give us an explicit function that we understand.

Â I want to emphasize once more.

Â Master theorem is not a framework for solving all recurrences.

Â The recurrences have to be of a specific form, satisfies that the conditions for

Â it to apply.

Â And the last thing we saw is that using this technique of sorting,

Â I can use it as a pre-pocessing to pre-process lists of, of numbers,

Â of strings and so on so that later when I apply other operations like searching or

Â comparing the two closes elements and so on.

Â I can, I can get that operation done in much faster amount of time.

Â