In this video I'll explain the mathematical analysis of the randomized linear time selection algorithm that we studied in the previous video. Specifically, I'm going to prove to you the following guarantee for that algorithm. For every single input array of length n the running time of this randomized selection algorithm on average will be linear. Pretty amazing if you think about it because that's barely more what the time it takes just to read the input. And in particular this linear time algorithm is even faster than sorting. So this shows that selection is a fundamentally easier problem than sorting. You don't need to reduce to sorting. You can solve it directly in O(n) time. I want to reiterate the same points I made about quick sort. The guarantee is the same. It is a general purpose subroutine. We make no assumptions about data. This theorem holds no matter what the input array is. The expectation, the average that's in the theorem statement is only over the coin flips made by the algorithm made inside it's code of our own devising. Before we plunge into the analysis, let me just make sure you remember what the algorithm is. So it's like quick sort. We partition around a pivot except we only recurse once, not twice. So we're given an array with some length n. We're looking for the ith order statistic, the ith smallest element. The base case is obvious. You're not in the base case; you choose a pivot p, uniformly at random from the input array just like we did in quick sort. We partition around the pivot just like we did in pic, in quick sort. That splits the array into a first part of those elements less than the pivot and the second part of those elements which are bigger than the pivot. Now, we have a couple of cases. The case which is very unlikely so we don't really worry about, if we're lucky enough to guess the pivot as the ith order statistic what we're looking for. That's when the new position j. Of the pivot element happens to equal I. What we're looking for. Then, of course, we just return it. That was exactly what we wanted. In the general case, the pivot is going to be in the position J, which is either bigger than what we're looking for I, that's when the pivot is too big or J. It's position will be less than the ith order statistic we're looking for. That's when the pivot is too small. So if the pivot's too big, if J is bigger than i that when we're looking for is on the left hand side amongst the elements less than the pivot. So that's where we recurse. We've thrown out both the pivot and everything to the right of it. That leaves us with an array of J minus I elements and we're still looking for the ith smallest among these J minus1 smallest elements. And then the final case, this is what we went through in the quiz and last video, is if we choose a pivot who's smaller than what we're looking for, that's when J is less than I, then it means we're safe to throw out the pivot and everything less than it. We're safe recursing on the second part of those elements bigger than the pivot. Having thrown out the J's smallest elements, we're recursing on an element of length of N-J and we're looking for the i-j smallest element in those that remain, having already thrown out the J smallest from the input array. So that's randomized selection. Let's discuss why it's linear time on average. The first thought that you might have, and this would be a good thought, would be that we should proceed exactly the same way that we did in Quick Sort. You recall that when we analyzed Quick Sort, we set up these indicator random variables, x, i ,j determining whether or not a given, pair of elements got compared at any point in the algorithm. And then we just realized the sum of the comparisons is just the sum, overall, of these x,i, js. We applied linearity of expectation and it boiled down to just figuring out the probability that a given pair of elements gets compared. You can analyze this randomized selection algorithm in exactly the same way. And it does give you a linear time bound on average. But it's a little messy. It winds up being not quite as clean as in the quick sort analysis. Moreover, because of the special structure of the selection problem, we can proceed in an even more slick way here than the way we did with quick sort. So, again we'll have some constituent random variables. We'll again apply linearity of expectation but the definition of those random variables is going to be a little bit different than it was in quick sort. So, first a preliminary observation. Which is that the workhorse for this randomized selection procedure is exactly the same as it was in quick sort. Namely it's the partition subroutine. Essentially all of the work that gets done outside of the recursive call just partitions the input array around some pivot element as we discussed in detail in a separate video that takes linear time. So usually when we say something's linear time we just use big O notation. I'm gonna go ahead and explicitly use a constant c here for the operations outside the recursive call. That'll make it clear that I'm not hiding anything up my sleeves when we do the rest of the analysis. Now what I wanna do on this slide is introduce some vocabulary, some notation which will allow us to cleanly track the progress of this recursive selection algorithm. And by progress I mean. The length of the array on which is currently operating. Remember we're hoping for a big win over quick sort, cuz here we only do one recursive call, not two. We don't have to recurse on both sides of the pivot just on one of them. So it stands to reason, that we can think about the argument making more and more progress as a single recursive calls operating on arrays of smaller and smaller length. So the notion that will be important for this proof is that of a phase. This quantifies how much progress we've made so far, with higher numbered phases corresponding to more and more progress. We'll say that the r select algorithm at some midpoint of its execution is in the middle of phase J. If the array size that the current recursive call is working on has length between 3/4th raised to the J times N and the smaller number 3/4th J+1 times N. For example think about the case where J equals zero. That says phase zero recursive calls, operate on arrays with size of N and 75 percent of N. So, certainly, the outermost recursive call is going to be in phase zero. Because the input array has size N. And then, depending on the choice of the pivot, you may or may not get out of phase zero in the next recursive call. If you choose a good pivot, and you wind up recursing on something, that has, at most, 75 percent of the original elements, you will no longer be in phase zero. If you recurse on something that has more than 75 percent of what you started with, of the. Input array, then you're still gonna be in phase zero even in the second recursive call. So overall the phase number J, quantifies the number of times we've made 75 percent progress, relative to the original input array. And the other piece of notation that's going to be important is what I'm going to call Xj. So for a phase J, Xj simply counts the number of recursive calls in which a randomized selection algorithm is in phase J. So this is gonna be some integer. It could be as small as zero, if you think about it, for some of the phases. Or it could be larger. So why am I doing this? Why am I making these definitions of phases and of these XJs? What's the point? We're gonna remember the point was we wanna be able to cleanly talk about the progress that the randomized selection algorithm makes through its recursion, and what I wanna now show you is that in terms of these XJs, counting the number of iterations in each phase, we can derive a relatively simple upper bound on the number of operations that our algorithm requires. Specifically the running time of our algorithm, can be bounded above by the running time in a given phase, and then summing those quantities over all of the possible phases. So we're gonna start with a big sum, over all the phases J. We want to look at the number of recursive calls that we have to endure in phase J, so that's XJ by definition. And then we look at the work that we do outside of the recursive calls in each recursive call during phase J. Now, in a given recursive call, outside of its recursive call, we do C times M operations where M is the length of the input array and during phase J we have an upper bound on the link of the input array. By definition it's at most three quarters raised to the J times N. So that is, we multiply the running time times this constant C this, we inherit from the partition subroutine and then we can, for the input length, we can put an upper bound of three quarters raised to the J times N. So just to review where all of these terms come from, there's three quarters J times N is an upper bound on the array size. During phase J, this by the definition of the phase. Then, if we multiply that times c, that's the amount of work that we do on each phase J sub-problem. How much work do we do in phase J overall or we just take the work per sub problem that's what's circled in yellow and we multiply it times the number of such sub problems we have. And, of course, we don't wanna forget any of our sub problems so we just make sure we sum all of our phases, j, to insure that at every point we count the work done in each of the sub problems. Okay? So, that's the upshot of this slide. We can upper bound the running time of our randomized algorithm very simply in terms of phases and the XJ's, the number of sub problems that we have to endure during phase j. So, this upper bound on our running time is important enough to give it notation, we'll call this star, this will be the starting point of our final derivation when we complete the proof of this theorem. Now don't forget, we're analyzing a randomized algorithm so therefore the left hand side of this inequality the running time of r select, that's a random variable. So that's a different number depending on the outcome of the random coin flips of the algorithm. Depending on the random pick it has chosen, you will get different random running times. Similarly the right hand side of this inequality. Is also a random variable. That's because the X J's are random variables. The number of sub problems in phase j depends on which pivots get chosen. So. To analyze, what we care about is the expectations of these quantities, their average values. So we're gonna start modestly and as usual, this will extend our modest accomplishments to much more impressive ones using linearity of expectation, but our first modest goal is just to, to understand the average value. Of an XJ, the expected value of XJ. We're gonna do that in two steps. On the next slide, I'm going to argue that to analyze the expectation of XJ, it's sufficient to understand the expectation of a very simple coin flipping experiment. Then, we'll analyze that coin flipping experiment. Then we'll have the dominos all set up in a row. And on the final slide, we'll knock'em down and finish the proof. So let's try to understand the average number of recursive calls we expect to see in a given phase. So, again, just so we don't forget. Xj is defined as the number of recursive calls during phase J. Where a recursive call is in phase J, if and only if the current sub array length lies between three-fourths raised to the J+1 times N. And then, the larger number of three-fourths raised to the J times N. So again, for example, phase zero is just the recursive calls under which the array length is between 75 percent of the original element and 100 percent of the original elements. So what I wanna do next is point out that a very simple sufficient condition guarantees that we'll proceed from a given phase onto the next phase. So it's a condition guaranteeing termination of the current phase. And it's an event that we've discussed in previous videos. Mainly that the pivot that we choose gives a reasonably balanced split. 25-75 or better. So recall how partitioning works, we choose a pivot P. It winds up wherever it winds up. And the stuff to the left of it's less than P. The stuff to the right of it is bigger than P. So 25 to 75 split or better, what I mean is that each of these, each, the first part and the second part has, at most, 75 percent of the elements in the input array. Both have twen-, both have at least 25%, and, at most, 65%. And the key point is, that if we wind up choosing a pivot that gives us a split that's at least as good the current phase must end. Why must the current phase end? Well, to get a 25, 75 split or better than no matter which case we wind up in, in the algorithm we're guaranteed to recurse on a sub problem that has at most 75 percent of what we started with. That guarantees that whatever phase we're in now, we're going to be in an even bigger phase when we recursed. Now, I want you to remember something that we talked about before, which is that you've got a decent chance when you pick a random pivot of getting something that gives you a 25, 75 split or better. In fact, the probability is 50 percent. Right? If you have an array that has the integers from one to 100 inclusive, anything from 76 to s, 26 to 75 will do the trick. That'll insure that at least the first 25 elements are excluded from the rightmost call and at least rightmost 25 elements are excluded from the left recursive call. So this is why we can reduce our analysis of the number of recursive calls during a given phase, to a simple experiment involving flipping coins. Specifically, the expected number of recursive calls. Now we are gonna see in a given phase J, is no more than the expected number of coin flips in the following experiment. Okay, so you've got a fair coin, 50 percent heads, 50 percent tails. You commit to flipping it until you see the head and the question is, how many coin flips does it take up to and including the first head that you see? So the minimum it's gonna be one coin flip if you hit a head the first time it's one. If you get a tails and then a head, then it's two. If it's tails, tails, head it's three and so on, and you always stop when you hit that first head. So what's the correspondence? Well, think of heads as being you're in Phase J, and if you get a good pivot, it gives you a 25/75 split. Call that heads. And it guarantees that you exit this Phase J. Just like it guarantees that you get to terminate the coin flipping experience, experiment. Now, if you get a pivot which doesn't give you a 25/75 split, you may or may not pass to a higher Phase J, but in the worst case, you don't. You stick to phase J is you get a bad split, and that's like getting a tails in the coin flipping experiment, and you have to try again. This correspondence give us a very elementary way to think about the progress that, that our randomized selection algorithm is making. So, there's one recursive call in every step in our algorithm, and each time we either choose a good pivot or a bad pivot, both could happen, 50-50 probability. A good pivot means we get a 75-25 split or better. A bad pivot means, by definition, we get a split worse than 25-75. So what have we accomplished? We've reduced the task of upper bounding the expected number of recursive calls in a phase J to understanding the expected number of times you have to flip a fair coin before you get one hit. So on the next slide we'll give you the classical and precise answer to this coin flipping experiment. So, let me use capital N to denote the random variable, which we were just talking about, the number of coin flips you need to do before you see the first heads. And, it's not very important, but you should know that these random variables have their own name. This would be a geometric random variable with parameter one-half. So you can use a few different methods to compute the expected value of a geometric random variable such as this, and brute force using the definition of expectation works fine as long as you know how to manipulate infinite sums. But for the sake of variety, let me give you a very sneaky proof of what it's expectation is. So the sneaky approach is to write to the expected value of this random variable in terms of itself and then solve for the unknown, solve for the expectation. So let's think about it. So how many coins flips do you need? Well for sure you're gonna need one. That's the best case scenario. And now two things can happen, either you get heads and that has 50 percent probability you stop or you get tails that happens with 50 percent probability and now you start all over again. Again you just put points until you get first heads. On average how many times does that take. Well by the definition of capital N you expect. The expectation of N coin flips, in the case where you get tails, and you have to start all over. So this one represents the first coin flip, the one-half is the probability that you can't stop, that you have to start all over probability of tails, and then because it's a memory less process, because when you start anew on the second coin flip having gotten the tails, it's as if you're back at time one all over again. So now we have a trivial equation, in terms of the unknown expected value of N and the unique solution, the unique value, that the expected value of capital N could have, in light of this equation, is two. So, on average if you flip a fair coin and stop when you get heads, you're going to see two coin flips on average. To make sure you haven't sort of lost the forest for the trees, let me remind you why we were talking about this coin flipping analysis in the first place. So recall in the previous slide we showed that XJ, and remember XJ is the number of recursive calls you'd expect to see in a given phase J, and we argued that the number of recursive calls you're gonna see is bounded above. By the expected number of coin flips until the heads. So this exact calculation of two for the coin flips gives us an upper bound of two for the number of recursive calls on average in any given phase J. So now that we've got all our ducks lined up in a row, let's wrap up the proof on this final slide. So, inherited from part one of the proof, we have an upper bound. On the expected running time. Of the R select algorithm. This is what we were calling star on the first brief slide In star, it looked a little messy, but we had the sum over the phases J. But we had two things that were independent of j: the constant c and the original input length n, so let me just yank the c and the n out front. And then we have this residual sum over the phases J. Of three quarters raised to the J remember that comes from our upper bound on the sub problem size during phase J and then of course we have to keep track of how many phase J sub problems we have solved that by definition is XJ. Now star was written as a rand in accordance terms to the random variables. Now we're gonna go ahead and take the expectations and again I have said this over and over but don't forget where's the expectation come from. This is over the random pivot choices that our code makes. So the expected running time of the algorithm is most the expectation of this start quantity. So like I said earlier, pretty much every time we're gonna do any analysis of [inaudible] process, we're gonna wind up using linearity of expectation at some point. Here is where we do it. Linear expectation says the expectation of a sum is just the sum of the expectations. So we yank the c and the n outside of the expectation. We yank this sum over phases. Outside of the expectation. We yank this three-fourths raised to the J outside of the expectation and then we just have the expected value of XJ, the average number of recursive calls we expect to see in HJ. Now on the previous two slides, we figured out an upper bound on how many recursive calls we expect to see in each phase. So first by the coin flip analysis, by the reduction of the coin flip analysis, this is the most expected number of coin flips N, which on the previous slide, we argued was exactly two. So bringing that two out in front of the sum, that no longer depends on J. So we get a most 2CN. Times the sum over phases J, of three quarters raised to the J. Now this kind of sum we have seen previously in the course. It came up when we were analyzing the master method and we summed up our running time upper bounds over the levels of our recursin tree. And if we're not in case one if we're in case two or three we had geometric sums that were nontrivial. They require a certain formula to calculate, so let me remind you of that formula here, when the three quarters are being powered up to the J. So this has value at most, one over one minus, the number that's getting powered, so in this case it's three quarters, one minus three quarters is a quarter check reciprocal, you got four. And the upshot is that the expected number of operations that this randomized selection algorithm uses to find the [inaudible] ordered statistic in a given input array, is eight times C times N. Where C is the, hidden constant in the linear running time of partition. And so that completes the proof. The input array was arbitrary. We showed the expected running time over the random choices of the algorithm is linear in N. That is, only a constant factor larger than what is required to read the input. Pretty amazing.
