Video 5-4: Linear-Time Selection
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-10, 12:39
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:02 What's left is the question whether you can also do this in the worst case linear time not just uh randomized or expected and uh to frame that question let me uh present two characters that will reoccur a few times in the module um just to kind of a bit um motivate where where certain things come from. So there's a programmer that is the practitioner uh who loves algorithms for their applications that they enable but doesn't maybe care about asmtoically optimal as much. He wants things that that they can implement and that actually work and that's it. And on the other side, uh maybe there's the more senior looking professor of computer science who um wants these elegant and definitive answers about eternal truths. In particular, he's after asmmptotically optimal solutions. And so sometimes these two disagree a bit on the goals. And in this case, um, our practitioner would maybe be happy with quick select for all intents and purposes. It gets the job done and it's so unlikely to fail, um, being fast that you'll never live to see it.
1:20 But you could still maybe be interested in the theoretical question whether you can do it without any randomization. Um maybe to jazz up the question a bit more. I assume people have heard of the question of P and NP and whether all polomial time algorithms uh whether all uh such problems have a polomial time algorithm. Uh still open still wide open and unclear. One question people have that is a bit more fine grain there is does it help to allow randomization? Can I solve more problems in polomial time if I'm only looking at the random expected case and allow picking samples all these things? And this is also mostly open and uh there's a few examples of problems where people know a good randomized algorithm but nothing deterministic even though experts rather think it's possible to always do it. Not constructively though. Okay, so let's see if we can do this problem in the near time.
2:24 And the answer is ultimately yes. And it's a rather simple algorithm um viewed from the right way. It would be very easy if we always had the exact median as the pivot because then we can guarantee that each step loses half of the elements. So I start out with a factor one for all the elements. The next recursive call gets me to size 1/2, then a quarter, then an eighth, 16th, and so on. And the picture shows you this converges to overall two, right? Proved by area geometric series. Maybe you've seen this before. I was just looking for an excuse to draw the spiral. Uh then the total cost would be at most 2n. That's linear. Unfortunately, that's wishful thinking because finding the median is the very problem we're trying to solve. So by asking for the solution to the problem to solve my problem, I cheated somehow. Still, this is not useless to look at because the the insight we can gain from that if we're not able to cut the input precisely in half, but at least we lose a constant fraction. That's good enough for this analysis. The spiral would be a bit more wide. So it's a one over one minus alpha factor instead of two. But still it's good enough to find some element of rank between uh not not very small not very large is good enough. So um split off an epsilon on both sides. Any element that is inside this range would be good enough for any fixed epsilon.
4:05 That sounds like an easier problem. You're not wishing for an exact rank, just most ranks actually work. That's roughly what what this algorithm tries to do. Now, still when it when it was published, uh that's what people tell about it. It was rather shocking that this works in hindsight is always easy. What does this algorithm do? Um let me show you uh the animation first. And while this is running, you can um you can see a bit more what what's happening. It's the same code uh just split up in two procedures. It picks groups of five elements, sorts them, and then swaps the middle one of these five to the left. So again, five elements, the middle one swapping to the left. Next five elements, take the middle one, swap that to the left. You keep going until you have uh the whole input covered with groups of five. That's all the green elements. Then for the last few uh we ignore those.
5:10 Now um one step back these these five elements this is a fifth of the elements right overall. And what have we paid so far? Well we went through the entire input and always sorted groups of five. Sorting five elements costs a couple of comparisons but it's some constant factor times n. Right? So, so far we've spent linear time, essentially one glorified pass with a little bit of local rearrangement, and we've taken the middle elements out to the left. Now comes the the cleverness of this algorithm. We'll recursively call ourselves on these green elements, these middles of five elements each, and try to recursively find the median of those. uh in in this case here we can we can do this with one step because it's only five elements there's a base case for the algorithm if I have five or less elements I'm just going to sort them so I've found the median of these middle elements of the groups of five otherwise known as this is the median of medians that's giving the algorithm its name median of medians algorithm and this element that I'm now found that I found whether this weird procedure that's the pivot I'm going to use for quick select.
6:36 So we're going to partition in the usual way and continue recursively just the same as quick select does. That is all. So um well we can we can let this run um just to see the animation but nothing interesting happens there. Just always when you ask for a pivot, you do this weird groups of five procedure.
7:06 Now why does this uh why does this work? The pivot we get from this has a certain guarantee because it's chosen from these groups of five. I always know from each group there's two smaller and two larger elements. And so I have a guarantee of how good or bad the rank of this element can get. And um that's best shown in this picture. Suppose you arrange the groups of fives as columns and then over the input uh all the columns next to each other. The pivot we eventually pick is among all the medians from the groups the median. So all these are smaller than this pivot element and all these are larger than the pivot element. But I know that these above this uh middle row these are also smaller than the pivot by choice of the sorting. So all of these elements in this red blob here are smaller than the pivot. All the elements in this other red blob are larger.
8:09 And how big are these red blobs? In width, the pivot is chosen to be essentially in the middle plus minus one give or take. So I have half of the elements that are left or right and I have among the columns three fifths that are good. So I have 3 fifths * a half * n roughly which of course is 310.
8:40 So I'm only left with 30% of the elements um that are on either side guaranteed which means the worst case for my recursive call is the other elements 70%.
8:53 So I'm I'm guaranteed that this pivot chosen as the median of the medians of groups of five always excludes at least 30% of the elements with a bit of rounding because I I may here have slightly picked um the element the pivot is is only uh closely to the middle and the last column is is excluded. But for large input sizes all of these uh are vanishing factors.
9:22 Okay, now that's still not enough to convince ourselves that the overall algorithm is linear. We should analyze it and then note that this algorithm is also rather complicated in the way it works because it's a mutually recursive procedure. The main method for selection calls this choose pivot. But choose pivot again calls main selection which calls choose you know this is uh the recursion tree looks messy. So effectively we have two recursive calls not one like in quick select. The first one is easy to analyze because here this recursive call we always have exactly a fifth of the elements may be rounded down because the last last incomplete group of fives we just skipped. So I'm I'm doing a recursive call on at most a fifth of the elements. And in the very worst case for the main recursive call here or here uh I'm going to do 70% of the elements. Now um the kind of uh less rigorous version of the analysis here says we're trying to show a linear upper bound. So let's just guess that the bound is linear and then prove it. So if the bound is linear then I can upper bound the contribution from these two recursive calls by one call to the sum of their sizes and that's 9 / 10. So I have a a recurrence where I pay a linear term and then I'm left with 90% of the elements in the worst case. So that is the same as our spiral before just with the worst constant.
11:08 And the overall time is linear. If you want a bit more rigorous of an analysis, you can use this fancy Rora master theorem because we have a recurrence of with two recursive calls with a different uh constant B.
11:24 And uh you can it's it's spelled out on the slide. But again, because the main theorem already is not part of the exam material, you don't need to know this. This is just if you find it more satisfying to see the full solution. Here it is. and you get um you can even work out the constant but that that needs to work out how much it costs to sort five elements.
11:53 Either way, we've um found an algorithm that takes linear time in all cases and doesn't need to resort to sampling. So this is uh is is the final kind of ultimate algorithm for for finding ranks or finding selecting elements by rank. Um in practice quick select is always going to be much faster. There's a I've not seen this algorithm really compete. It is faster than sorting the entire input. So it's somewhere in between. And if you really need this strong guarantee of a deterministic algorithm, maybe it's worth implementing this one. Most of the time, uh, it won't.
← Video 5-3: Selection by Rank, QuickselectVideo 5-5: Long Multiplication →