Video 2-17: Multiple selection algorithms + adaptive lower bound

0:03 Or let's uh kind of tie this up in one one big black box and just remember that you can do in linear time the selection algorithm of a single rank. How can we solve multiple selection?

0:16 Clearly, I can just call the single selection multiple times. Ta-da. But uh that's a bit wasteful if you think about it. If you do Q calls to this selection algorithm, that's Q times linear. Uh but in a way um is wasteful because the If you're trying to get this rank and this rank and this rank, remember if I select the middle one first, I already know that all the elements smaller than this one have been identified and I I can even make the algorithm put them on the left. So if I call the second selection algorithm on the entire array again, that's kind of stupid. I could have called it just on this part. So let's do that, right? Uh formally, this is a divide and conquer algorithm. Where um I'm There's two parts of the input now. I have an array of elements and I have an array of ranks that I'm trying to find.

1:23 So I can do divide and conquer over either of them. I could do divide and conquer over the ranks. So find the middle of the ranks. Part Do a selection call for this one and partition the array around this one. That's what I'm my previous picture was suggesting. Now let's draw a bit more general of a situation. It could be that the ranks are a bit more clustered on one side. That is is possible. Now I'm going to take the middle one first. So, I'm going to split the array here. But either way, I'm going to reduce the number of ranks I still have to look at in each recursive call by a factor two. So, I'm going to look at this for another rank. And then on this one for another rank. Here, I don't even have to recurse because there's no rank left. I got lucky. And here, I'm going to do another recursive call here and then another recursive call for this one. Here, I got lucky again.

2:29 Uh how many times do I have to do this? Well, uh as long as I still have ranks to search left. And they reduce by a factor of two in each in each step. So, well a million pages too far. Let's jump back.

2:55 Uh that's a bit too far back. That's better. such steps before I'm out of ranks. And in each step I'm going to at most look at the entire array. I might be lucky and some elements are left out. Maybe it would be on the safe side. Let's say plus one because the rounding might mean I need another round, but then an incomplete one. So, certainly after uh n log Q total time, I'm done.

3:37 Much better than n times Q. Now, this was divide and conquer over the ranks. Mhm, let's try to do the other one just for completeness, shall we? I could also do divide and conquer over the elements. What would that look like? Well, I'm going to find the middle, the median of the elements. And now, there might be more ranks on one side than on the other. I'm just going to ignore that. And I'll continue on the left. So, here I'm going to again split right in the middle. Don't care where the other ranks fall. Same here.

4:21 So, this this first looks a bit more wasteful. In particular, um I might be lucky here and can stop. But here, I'll have to go for a good more time. And certainly, my my depth of the recursion may be higher than log Q.

4:41 So, maybe this was lucky and it right hits here. This needs to continue. I'm growing tired of finishing the picture. Let's pretend this were individual elements already.

5:00 The height here, well, it's at most log n, that's for sure. Uh also, it's at most log it's at most Q. Well, that's not even true, right? I'll strike that. In an extreme case, you might have all the ranks clustered on one end, and it might take you a long time till you get there, even if especially if Q is small. So, at first, it looks like this is maybe the the less good algorithm.

5:43 Now, you can show that this is also n log Q, and we'll look at this algorithm um in much more detail later. Uh let me maybe finish the picture here. Um How would you You can You can prove this the following way.

6:19 If you continue for log Q plus one steps, let's be generous again. Which means uh I've gone down so far that no matter what I do, I have now two times Q subproblems.

6:50 All of the same size roughly. All of size n divided uh whatever that is, two times Q. So, the trick is by pigeonhole principle, if I have Q ranks to find, there will be Q subproblems without ranks. There might be more if they cluster into uh some subproblems.

7:28 So, this case here where I could stop because there's no query rank inside anymore. If I go down for log Q plus a little bit, I'm sure that I've lost half of the elements. Okay?

8:12 So, if you want I I can view this as one big divide and conquer step. I do log Q rounds of partitioning, each with total cost N.

8:39 Let's make it N times log Q. And after that, I've reduced my input size to N half. So, the total cost for size N is is order N log Q plus the same algorithm on N half.

9:00 Let's say upper bounded. So, by the same argument as before, uh we're only going to get uh a geometric series here. So, I get the same N log Q that I had for the first type of divide and conquer. Now, it feels like the constant is got to has to be worse because we're we're getting at least a factor two from this, uh we've already wasted one extra recursive step, etc.

9:36 So, it feels like um, maybe the two are equally good with respect to big O. But, clearly this seems to be the saner algorithm. But, fine. Um, both came down to n log q. You can also prove that you in the worst case need omega of n log q comparisons to solve this problem. So, um, we have a matching lower and upper bound. We even have two algorithms achieving the upper bound. What else could we hope for?

10:12 Well, we're in the chapter on adaptive analysis. So, let's look a little closer at what this problem could, uh, have as input. And it turns out, depending on how the ranks are clustered, the lower bound is not actually n log q, but could be much lower. So, our algorithms don't necessarily achieve the lower bound in the general case. Um, the precise statement is given here.

10:48 So, I've already introduced the query ranks before from the multiple selection problem. To formulate the balance in a nice way, we have to look at the gaps between the queried ranks and the outside. So, we add some uh, some boundary ranks that are not real ranks, but are just there to make the definitions nice.

11:29 Looks Looks about right. Uh, oh, n plus one. So, 17 then. So, you just pretend there was another queue. Hold on. All the Yeah, okay. Uh the gaps So, okay. An off-by-one that you can always get into. Is there a pivot value between the gaps or not? Here, the answer is no. So, uh Yeah, seems right. >> [snorts] >> So, if you define these these gaps deltas as the differences between consecutive ranks, then you can define this uh gap entropy just this sum of these of these quantities. The gap times log of n divided by the gap. And this has the flavor of an entropy if you you look at say some PIs defined by delta I divided n. Then an entropy for these PIs Q plus one. And first of all, note that these sum to n uh sum to one because the delta I sum to n. That's not written anywhere, but I think it's useful to state.

13:07 This is by definition. It's a telescoping sum. And uh I start I end with n plus one and subtract zero, which clearly isn't n. Maybe this is n, right? Uh I'm I'm in the same off-by-one. Let's Let's keep it like this for now. The The plus minus one will not make a big difference later. So, these PI's sum to one and the entropy of such uh set of probabilities would be the probabilities times log of one over the probabilities. And if you insert that what we've defined these PI's PI's guys like you see that up part from a factor one over n you get precisely this B. That's why it's called an entropy even though there's nothing random uh going on here. Now, the claim is that for this multiple selection problem, you indeed need roughly this B many comparisons, whatever it is.

14:29 Uh the intuition that it is an entropy also hints at some some properties of this function. Uh let me maybe state this first before we prove the bound. Uh note.

14:48 So, this B is largest when things are uniformly distributed, so all the deltas are the same. In that case, we get uh Q plus one times the same term.

15:14 And the delta I are just n divided Q plus one. And this is n divided n divided q plus one So that cancels. Uh this cancels. This cancels.

15:32 So we have n times log q over q plus one. Aha, that looks familiar, right? That's what I said before. In the worst case for this problem, worst case meaning the ranks are all equal equidistant. You need n log q comparisons. What's the other end of the spectrum for b?

16:00 In general, entropy could be as close to zero as you want. Uh but here because our deltas are have a minimal size, they're at least one. The most extreme case is that all the ranks are say as small as possible. They're the first 1 2 3 up to q. And then we get q contributions where the delta is one.

16:35 And we get one contribution for all the rest. So essentially a rough n minus q and then log n divided n minus q. Not sure we can do a lot there. It's q times log n.

16:58 Note the fun symmetry here, n log q and q log n, but of course q is often much smaller than n, so this is a way smaller term. And this n minus q log n minus This is a bit unclear what it is in general. If q is small, this might be just a linear term.

17:28 But this could get fairly small, right? Uh Is there a nicer way to write it? We could rewrite it using the Taylor series expansion. I don't know if that's leading anywhere.

18:10 at the most extreme, it might just be log Q uh order Q because these cancel. Uh if if Q is small enough. At this point, the lower bound becomes a bit uninformative because uh maybe for comparisons, this is sensible. Uh but if you if you look at this problem, any algorithm that solves this problem needs to be allowed to read all the input. Otherwise, you can smuggle in a very large or very small element that invalidates the output of your algorithm. That's why we have this this term here in the running time, whereas for comparisons, we can only claim roughly B.

18:55 So, this bound B can be somewhere between N log Q and Q log N. Let's ignore this order Q. That's dominated by the first part. And if if you think about Q can be, say, a small constant, then this is between log n and n. Very big range. So, where your queries are matters for this problem.

19:25 Let's also prove this this lower bound of B. The proof is much less messy than this result may may suggest. And maybe this warms your heart a bit more for this gap entropy.

19:53 Okay. I now remember that I've typed up the proof, so we don't have to write it. That speeds up things a bit. Um Suppose by for sake of contradiction, we had some multiple selection algorithm that correctly solves this multiple selection problem and hypothetically this would be faster than the lower bound, but we don't need the contradiction really. Let's just say A is such an algorithm and we'll derive a lower bound for its cost. We run A using some ranks. That's what it does and it outputs to us these uh order statistics of what are The notation here just means these are from the input X1 to Xn is the uh I think this doesn't even make sense, this notation. Uh this should be X R1 up to X Rn RQ.

20:58 Okay. Now, if this is a correct selection algorithm, what I've said before about this adversary argument means every other every other element you know where it lies with respect to these returned elements. Again, XR1 up to XRQ.

21:24 You know where it falls um among those. That means we can turn A into a sorting algorithm if we help it a bit by essentially finishing off sorting. So, A took our certain query ranks.

21:44 And it already made sure that it learned for every element where it falls. So, we might as well put again the elements in this partition form. These are all less than R1, etc. And then all I'm going to do is uh I'm going to call a sorting algorithm to finish off sorting in these intermediate parts.

22:16 So, there's going to be a sorting algorithm that's called that's called on this first part. And a separate sorting method a sep- separate call for the second part and so on. And these are um these are just delta minus one elements uh between these two ranks by definition of the deltas. Delta I minus one.

22:47 Now, a sorting algorithm, if it's comparison-based, has to respect the lower bound for comparison-based sorting. It needs to distinguish n factorial different orders. So, log of n factorial is a lower bound. So, this total cost of comparison must be at least log n factorial. How does the comparison for our sorting algorithm come about? It's should be greater than log of n factorial. But um I'm subtracting what I spent to sort these these intermediate parts because that's not A's fault. A didn't pay for this. So A uses that many comparisons which is at least what you need for sorting, but then you subtract again what you need to sort these intermediate bits. And then you can just rearrange. We'll use that log of n factorial is roughly n log n with a linear error term. We use the same here for these deltas.

23:54 Yeah, okay. I have to split it. That's the same we'll continue the proof uh from here. Um with a bit of same same analysis trick as as before this that log of 1 + x is order x. You can rewrite this x - 1 log x - 1 as x log x with a little error term. We'll apply this inside the sum to get to this part. Again, there. Too far away. Okay.

24:35 So we get n log n minus this sum with a little error term. And now you combine these two parts. Note that the delta i sum to n, so I can split this n up into into the sum of delta i's. Then I have log n minus these log delta i that becomes this part. And that's our B, right? This this sum is precisely our B. And we have a linear error term uh that's left.

25:07 So, this this lower bound term, this B, is fairly natural if you if you remember where it comes from. It's just what you were what you're paying for sorting the entire array minus the sort the parts that you don't have to sort if you're just doing selection.