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. So, this again we go back to the issue of we have, we have a recurrence and the recurrence, is of the right form for the master theorem. Again remember the master theorem applies to recurrence of the form T of n equal a of T of n divided by b plus f of n. Where f of n is O of n to the d, right? So here this was the kind of recurrence that it applies to. What is a? It's 1. What is b? It's 2. What is d? O of 1 is 0 of n to the 0. So d is 0, right? So for binary search, a is 1, b is 2, d is 0. Remember, for merge sort, it was, a is 2, b is 2, d is 1, okay? So binary search has a little bit of a difference with the, with the merge sort. Remember, for the master theorem, the first thing to check is. How does a compare to b to the d, a is 1, b is 2, and d is 0. 2 to the 0 is 1, 1 equal. So we have a equal b to the d. Remember the master theorem says that if a equals b to the d, then T of n equals all of n to the d log n. In our case, d is 0. So it's of n to the 0 log n. So the running time of my, of binary search is actually log n. 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. So binary search is O of log n, linear sear, search is O of, of of n. Again, binary search is O of log n. 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. 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.
