CS 566 – Efficient Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-10, 27:19

Click any sentence to play from there.

The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.

0:03 Time for algorithms. We've uh beaten the analysis of recurrences to death. Now let's uh try to apply it to some interesting problems. The first of these problems is the question about determining order statistics. Finding an element by rank, the other name, selection by rank. Uh it's a standard task that you may have in some some data science applications. Um there's various things if you have uh a collection of numerical data that you can do to summarize that u cloud of numbers. You can for example compute the mean or standard deviation or maybe the minimum and maximum or you can plot an entire histogram to get a a summary statistic for that data set. right now. Um one one common or popular way to draw such a summary statistic is this box whiskers plots where um you actually show something on top of that. You also show the median and the quartiles of the data set which is the values so that say a quarter of all the elements are smaller and three quarters are larger. That's the lower quartile. And the median is the value well that half is below, half is above. And if there's a lower quartile, there's an upper quartile where 3/3 are below.

1:26 All of these are called order statistics because they don't talk about really the individual values. They don't like a mean sum them up or something like this, but rather they just look at the relative ordering. And of course you know how um mean and median give you a different insight into the data. Both are useful in principle. So all of these above are very easy to compute in linear time with just a sweep over the data. Basically you sum things up or you find the minimum maximum. It's all relatively easy. For histograms maybe you want to do some some clever dictionary data structure. But for the uh order statistics it is if you haven't seen the solution a bit unclear how to compute them in in an efficient way an inefficient way. Um okay let me formally say what we want first. Um that's the algorithmic problem and uh I try to be a bit strict about this. An algorithmic problem always have some some inputs and then some goal. Yeah, we should state that explicitly. So what's given here is an array of numbers and numbers and uh another number the rank that we're looking for or the position that we're looking for and the goal is easiest to formulate as as this that also handles duplicates and all that. Suppose I take the array and sort it. What would be the element at position k in that sorted list? what's the value I find at position K in the sorted list. That's the task we're trying to solve. And it generalizes all these uh special cases above the median.

3:09 You may want to pick n half rounded down or the upper median rounded up if uh for n is even. Both can make sense uh for n. Yeah. Um because this is we're we're starting with with zero.

3:29 um then it's not rounded but uh plus one um for the quartiles it's it's n /4 roughly and then rounded minimum and maximum is also the contained as a special case and of course um the definition of the problem already tells you how you could solve it. One possible solution is to just sort the array fully and then pick the element from the position k. That does the trick. But the question is, can we do better?

4:19 You've seen many uh general strategies how to do this in n login time. If we don't know anything about the numbers, that's also the best we can do, right?

4:37 So the question is can we do better than that? That's n login and linear may be possible and is possible. the the key observation on how to make progress there or how to derive an algorithm is that um the inverse problem is easy. If I give you an element and ask for its rank, that's easy to do. You just count how many elements are smaller and how many are larger. So if I give you the median, if I somehow magically guess it, you can count how many elements are smaller respectively larger and then just say yes, that's the median. Good. Well done. Now uh if I give you some element and the rank turns out not to be the one you have you want then you're not done yet but at least this is easy to do in linear time. The inverse problem here's the rank please give me the corresponding elements seems harder and it's a bit harder uh but not um in terms of the theta class you need. And the the trick is a divide and conquer algorithm if you like. We pick some element because we know nothing about the input and determine its rank. And then there's three cases. Either I'm lucky I guessed exactly the element that I I wanted in which case I returned that and I'm I'm done. The other option is that my value is too small or too large. If the rank I found is smaller than the rank I wanted, well then all elements that are even smaller than this element that I picked are clearly useless.

6:10 So all the J + one elements including this guy A of B can be excluded from further consideration and similarly symmetrically if you have too large a rank and based on that we can divi deise a recursive algorithm and this is called quick select. It's called quick select because it does something rather similar to quick sort but it leaves out one of the recursive calls. Um so it's a recursive procedure here has this additional parameter k the position we want to select then um if we're essentially out of uh elements then we just return the leftmost and this is this assumes here that uh k is equal to l.

7:05 Uh otherwise you return some nonsense. you would want to have some some uh range check for your parameters in an actual implementation. If we have not yet reduced it to one element, we choose a pivot and again we have the same choices as when we discussed quicksort to do that and we call the partition function literally the same as in quicksort which returns us the position that the pivot landed in and that is the pivot's rank. It's the very same thing because by definition, partition puts the pivot element at its final landing position in the sorted array. So picking that index is the rank in the entire input. And then we just check if what we got here is what we wanted, then we return it. Otherwise, we're in one of those two cases and we have to do a recursive call. So for example, for this case, if J is smaller than K, I'm going to exclude the small elements. So the recursion is on the right part.

8:01 Everything left to the right of the pivot up to the right end point is where we do the recursive colon. Okay. Um a rather innocent algorithm and first we can improve it a little bit just in terms of the performance that it has in practice. This is called a tail recursive algorithm because the only recursive calls it does are always the last thing it will do. Um I think here's a return missing right in both cases. Uh this should be return and this should be return. Same I have to okay copy paste same mistake. Well, in each of these three cases, I want to just call my recursive call and return whatever that returns. It will eventually return something here. So, this is always going to be the last thing this current recursive call does. So, I can forget the stack. The stack frame for the current call is no longer needed. I can just immediately jump into this. And so, you can rewrite the method as an iterative method very easily.

9:13 uh this tail recursion elimination I don't know if people know or if if this was discussed if you have some functional programming language um this is usually one of the earliest things they built in so that it's automatically done by the runtime otherwise functional languages are rather rather slow but with tail recussion elimination they often get away from um substantial slowdowns so here this is done manually you can write it iteratively. Now, l and r the parameters here are just variables and you have a a loop where um unless you have a single element, you just do what you've done before and you adjust the parameters as here in the recursive calls. It's even a bit simpler this way. Yep.

10:14 Ah, I see. So, you're saying uh for the same data set you need ranks several times. Uh yeah, that there's a trade-off. That's right. Um you said we can use a binary search tree. That depends if if the data set is static, you can just sort it once and then every uh select operation is just an access. If the data set changes, then you want to use a binary search tree. Here the idea is what if you um if you're given this data set once and you want to do maybe the median and the two quartiles but not a ton more. Uh but that's that's correct. If you do more than login such calls, you could have sorted at the same cost. So you might as well do that. Uh there's this cute combinations of this idea where um um maybe also a good exercise that uh if you know you're going to do several recursive several select calls on the same input, you can remember where you've had pivots in the past and reuse them. Then you get the best of both worlds that if you do enough queries, the thing will be entirely sorted.

11:22 But uh if you only need say the small values ever then you'll not sort the other parts but you still get those fast. There's a dynamic version of that that's called lazy search trees. That's something uh we we invented at some point. The data structure there gets a bit more complicated. Uh but you can see you can hear about it in advanced data structures if you want. Bit of self advertisement. Um, yeah, only next winter again, I think. So, usually you would want this iterative version. If if you stick with plain quick select because you only do a few isolated calls, this is going to be faster. But, uh, we'll stick with the recursive version because it's a bit easier to match to the recurrence because we want to analyze how long this takes.

12:16 So, let's stick with this recursive version. And as the cost model here, pick just the number of comparisons. This is coming from the partition here. So you could also say the number of element visits if you want it more in line with the previous analysis from the sorting chapter is coinciding here. So conveniently it doesn't make a difference. What is a big pain in the back is these two parameters. the algorithm has a a size of the array or the range that we still look at and this second parameter k. So here we have something nasty where uh we have to deal with two parameters. Um in the worst case like quick sort this method is really bad. Suppose we try to find the minimum which really you should do just by finding the minimum in the special case pick keeping the minimum but you might call this function with k equals zero. Um if you're unlucky your pivot is always the largest element in the list. So you always do a full round of partitioning.

13:27 Chop off the last element and do a recursive call on one element less. And so it takes you all the way down. So you see you get this quadratic behavior. That's just as bad as in quicksort. Even though we didn't do the second recursive call, it turns out here it doesn't matter. The second recursive call would always be empty. So in this in this really bad case, we pay quadratic time.

13:57 Just as in quicksort, the average case is very far away from that. And the typical case is also far away from that. typical in the sense that if um the input is is randomly ordered either because it's it's random from the start or you explicitly randomize you uh shuffle the input then with high probability even you're very far away from this bad case. Okay. So how can we at least get a bound for the average case? I'm only going to sketch the analysis here. Again, this is something I'm not expecting you to uh do this on a new example in the exam. That's too much. Uh but uh I want I want to show that you can rigorously analyze this. So tn of k say is the expected cost when we choose the pivot uniformly at random. Then it's the same as having a random input.

14:54 We can formulate a recurrence for this. It's a bit beastly though. tn of k always pays n comparisons for the partition and then we have a random choice of which rank the pivot got essentially the return value j here the rank of the pivot could be anything between 0 and n minus one and each happens with probability 1 / n and then I have different cases here in the in the sum if my um rank happens to coincide with the k with the rank I'm looking for, I pay nothing extra. Uh, by the way, this um this notation here, Iverson bracket just says this is one if this condition is true and zero otherwise.

15:52 Uh, and you can just take this as a as a term that you multiply things with. It's convenient to write uh case distinctions in line, right? That's what we're doing here. So this this kind of just cancels because it's multiplied by zero. I just put it here there to explain the case. If k is smaller than r, then we have the right recursive call. So we have the uh r elements that are um sorry r is larger the pivot is larger than the value we seek. So uh we go to the left recursive call. In the left recursive call, there's as many elements as are smaller than the pivot. So r put k as the same same relative rank. If the rank I'm looking for is larger than the rank of the pivot, that's the right recursive call. There I have n minus r minus one elements and I have to adjust the parameter r to be k to be back in range because I'm taking the small elements away.

16:53 This is very much in line with when we talked about augmented binary search trees. Okay, that's that's the recurrence. This is the precise way to determine the cost. Unfortunately, this is rather beastly. It's not clear how to solve this. And in general, with such a recurrence, you shouldn't expect that to have a precise solution. It turns out here it it actually has a precise solution that uh Don can figured out at some point. I'm not going to show this though. It's just a is a long long term. It exists if you want to look it up. Uh but it doesn't generalize any anything beyond this. Let me instead give you an upper bound that does generalize. So um this kind of trick you can apply also in other scenarios. That's again just the recurrence we had. Uh what we'll do is we want to really get rid of this parameter K. Let's just upper bound our t and k. And clearly an upper bound for t and k is to pick the largest of the values for all k. So I'm going to take the maximum of all possible values k and call that t n hat.

18:05 Okay. Um clearly uh in my in my recursive part here I always have these two terms. So the sum here let me take the entire sum. This I can upper bound by element wise taking the largest and I don't know which of these two is larger in general. It's a bit hard to say but let's just say one of them is larger. I take the maximum uh that so far doesn't seem to help that much right but uh we can further upper bound this where again here I'm going to replace this tr with some k that we don't know much about by its upper bound namely t hat of r And same for this term. Again, this k uh looks looks nasty. Let's not worry about it. Let's upper bound it by just the the size of the uh inputs uh length of the array that we recurse on. And what we've done now is from from our t of n we found a recurrence that we can now uh formulate for our tn hat.

19:44 Our tn hat does this first recursive call. It's it is equal to one of those uh t and k. So I'm using the recursive call there. And then substitute on the right hand side this upper bound. So now I have a recurrence that just has one parameter and the K is gone. That's one first step.

20:07 Now this is still a nasty recurrence because it still has this full history flavor where I'm I'm summing over all of previous values and then I'm taking the maximum of two things is a bit hard to handle. Let's make our life easier and do um in in algorithm and data structures I called this trick that uh quick select throws a tantrum.

20:41 What I mean by that is uh we try a random pivot and if that nicely partitions our input, meaning it ends up somewhere in the middle half, then we're happy and we continue.

20:58 That's the middle half is. If it's outside the middle half, I'm going to get very angry and just shuffle my input and start from scratch for this recursive call, which means there's only these two options. Um, now, um, I'm further upper bounding because this algorithm is clearly stupid, right? Throwing a tantrum is never worth it. Sometimes you can't help it. Uh, but you're never going to save effort by doing that. always you would have made more progress by just after paying the cost for the partition go with what you found. It reduces your input a little bit at least. But if you instead just decide to start from scratch, you're only going to pay more. So the cost of this hypothetical quick select with a throws a tantrum algorithm is this TN tilda.

21:48 And that's always an upperbound for our original one. And this has a nicer form because the probability that my pivot lands in the middle half is around 1/2 and the probability that it lands outside is 1/2. So I have these two different outcomes that can happen and they're random. We take the expected value. I always pay n for the partitioning step. In the unlucky case, I make zero progress. I'm still at n elements. And in the lucky case, I make progress depending on where the pivot lands. But in the worst case of the good cases, I'm left with three quarters of the elements. Namely, if I'm if my pivot lands here and I have to recurse on the larger side, that's still this is one quarter, this is three quarter, right? So I'm left with three third three quarters n elements.

22:43 That's an upper bound for our upper bound for the actual cost. And this thing we can solve because you can just put this to the other side and multiply by two.

23:05 Then you get our tilda n less or equal 2 n. And this just stays. That's the four. And then finally we're in the realm where we can apply our known machinery. So again in nicely printed that's the recurrence you get. Uh if this is upper bounded you can define a new function that's precisely given by the recurrence if you worry about this upper bound. And for that we can finally apply the master theorem. So let's uh remember how this worked. That's our f of n. That's our a here is one. Our b is I'm dividing by 4/3.

23:54 It's a bit inconveniently written for that. Uh nevertheless, our log base b of a is going to be zero because uh a is one. So we're comparing our f of n which is well theta of n ^ 1 with our c which is zero. So clearly this is uh one is way larger than zero. So we're in the case where the topmost pole dominates everything and so um tilda of n is linear or because it's just an upper bound here. But that's good. We found a linear time method for finding the rank, right? That's what we wanted. It's after all of this only the expected case. So, uh we have we had to assume that we pick a random pivot and that we're happy with just the expected case. Um but that's at least something.

25:10 Let's wrap up on this part. Um quick select overall works really well. It has this bad worst case But apart from that it ticks all the boxes expected linear time. It doesn't need extra space. The partitioning you can do just as in quicksort in place. And uh you can you can tweak the method if you care about finding median and quartiles in one go. Uh conceptually very easy. As long as there are subpros that contain a rank you care about, you do a recursive call. And if there's ranges with no rank inside that you care about, you do not do the recursive call. Formulating this as a proper algorithm is what's behind this last thing. Uh that's also not not hard to do. And it it saves a bit over the alternative of just calling the algorithm three times.

26:00 Okay, that's all good. Um you could even further improve this algorithm by trying to pick a really good pivot. And here this is a difference um from quicksort. We've talked about this a little bit. With quicksort it makes sense to pick the pivot not completely random but maybe take three elements and take the middle element as pivot. That has a slightly better chance to divide the input evenly and helps. Now for quick select you actually want something different because if you're looking for say the minimum element or something close to the minimum I don't want to split the input in the middle. I want to split rather for far to the left just a little to the right of the element I'm looking for. Then in one step I exclude almost all elements not just half of them. And that's what's behind this um Floyd revest algorithm. It essentially uses a fairly large sample and then tries to find elements just around the rank that you're looking for. And that essentially gets you to this optimal comparison cost. Uh again, this last bullet you don't need to know. Uh but if you're wondering how far you can push the idea of quick select, that is kind of the answer. Also an old result.

← Video 5-2: The Master TheoremVideo 5-4: Linear-Time Selection →