# R4. Randomized Select and Randomized Quicksort

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=QPk8MUtq5yA
**Transcript page:** https://www.withtranscript.ai/video/QPk8MUtq5yA

## Chapters

- 0:00 — Chapter 1 (0:00)
- 3:03 — Chapter 2 (3:03)
- 5:19 — Chapter 3 (5:19)
- 6:23 — Chapter 4 (6:23)
- 8:23 — Chapter 5 (8:23)
- 9:09 — Chapter 6 (9:09)
- 9:49 — Chapter 7 (9:49)
- 11:43 — Chapter 8 (11:43)
- 12:37 — Chapter 9 (12:37)
- 13:25 — Chapter 10 (13:25)
- 14:03 — Chapter 11 (14:03)
- 15:49 — Chapter 12 (15:49)
- 17:08 — Chapter 13 (17:08)
- 17:56 — Chapter 14 (17:56)
- 18:40 — Chapter 15 (18:40)
- 19:36 — Chapter 16 (19:36)
- 20:27 — Chapter 17 (20:27)
- 21:55 — Chapter 18 (21:55)
- 22:50 — Chapter 19 (22:50)
- 24:23 — Chapter 20 (24:23)
- 25:15 — Chapter 21 (25:15)
- 26:21 — Chapter 22 (26:21)
- 26:47 — Chapter 23 (26:47)
- 27:32 — Chapter 24 (27:32)
- 29:07 — Chapter 25 (29:07)
- 29:57 — Chapter 26 (29:57)
- 31:19 — Chapter 27 (31:19)
- 32:18 — Chapter 28 (32:18)
- 33:04 — Chapter 29 (33:04)
- 34:03 — Chapter 30 (34:03)
- 35:04 — Chapter 31 (35:04)
- 36:15 — Chapter 32 (36:15)
- 36:57 — Chapter 33 (36:57)
- 39:20 — Chapter 34 (39:20)

## Transcript

**[0:00]:** The following content is provided under a Creative Commons License. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu.

**[0:21]:** Okay, so today we're going to analyze uh two random algorithms we've seen in the last lecture. Uh randomized median and randomized quicksort. But before I go into that, uh so I'd like to make a correction in problems set two. I think you all got feedback from that. Uh so it's the second problem where you're asked to combine B-trees.

**[0:51]:** You have a uh two B-trees T1 and T2, each with some children. Uh we're giving you a another element K, and we ask you to combine them. So, uh if they are the two trees are of the same height, uh how do you do that? Does anyone want to share his or her answer?

**[1:13]:** Go ahead.

**[1:17]:** Yeah. Yeah, exactly. So, you put K here. And if this is too full, you split. So, uh why do I have to do this? Can I simply just make K my new root and do this?

**[1:38]:** Go ahead.

**[1:42]:** Yeah, exactly. So, for B-tree, the requirement on root is slightly different for uh from the requirement for the rest of the nodes. So, this may have too few children. It is not a valid uh node. It's not a valid internal node. But this our solution actually made a mistake in the second part. Uh in the second part, we're saying so T1 and T2 their height are uh different by one. Our solution says put K here and make a pointer. Exact exactly the same problem. Does everyone see that? This may not be a valid internal node. So, what's the correct solution? You put K here and combine it with the last child of T1. And then you may have to split and split again. Okay? Everyone happy with that?

**[2:38]:** Okay. Now, today we are going to look into randomization.

**[2:45]:** Uh specifically, we have seen two algorithm in class. Uh I'll just call them quick find and quick sort.

**[3:03]:** So, quick find is a slightly generalized version of median finding. Uh in the very first lecture and recitation, we have seen a non-randomized version of quick sort. So, we divide them into groups of five.

**[3:26]:** And we find the median of each group, right? And then find the median of the median. Depending on whether you are smaller or larger, we drew a funny subproblem like this. Anyone remember that? And we analyzed this runtime um where our recursion does 1/5 plus some 7/10 or something like that, and we show it's worst case O of n. So, that's a smart algorithm. I'll give you that, but it's just complicated. You have to uh divide them into groups and do well. Several recursive calls. And also, let me digress a little bit. Uh there's a very interesting point regarding this worst case uh worst case O of n algorithm. Has anyone wondered why we use groups of five? Why not groups of three?

**[4:23]:** Algorithm should work in the same way, right? If we take out this first row and this last row, we can still find the median, which is just the second element in each group, and find the median of median. We still have a subproblem look that look like this. Exercise. And it turns out uh if we use groups of three, when we solve the recursion, it doesn't solve to O of n. It solves to something else. Okay? Now, uh end of digression. Let's get back to the randomized version. So, how does the randomized version work? It's uh much simpler. We have an array uh let me call it find uh in a array A, which which is of size n. And we want to find the ith largest or smallest element in it.

**[5:19]:** So, what we're going to do is that we'll pick a random element X in this array. And then we'll put all the uh smaller elements smaller elements on this side and all the larger elements on that side.

**[5:44]:** Now, uh cuz I'm picking a random one, so this X can be anywhere. If it is the kth smallest element uh from the left, then what do I do next?

**[6:05]:** My goal is to find the ith smallest element in this array A.

**[6:23]:** Okay, if it's if I is less than K, then my element is on this side, right? So, I should find Okay, let me define this to be the left array, this to be the right array. I should find the in the left array, what is its size? It's K minus one. Make sense? This is K minus one, and that is n minus K. Plus one element in the middle. Um

**[6:58]:** So, what's the last argument in that function call? It's I. Okay? So, on the other hand, if I is greater than K, then I should go to my right half. Its problem size is n minus K. So, what's the last argument?

**[7:26]:** I. Agree? I minus K. Right? Okay. So, of course, if I is equal than K, then we just return X.

**[7:42]:** Now, obviously, uh this algorithm's runtime depends on our luck. Depends on this choice of K. If K is roughly in the middle, then we reduce the problem size by roughly half, right? However, if K is zero or close to n, then we only reduce the problem size by a little bit. So, it's it's impossible to give a definite runtime. Uh so, what we opt to do in random in randomized algorithm is that we analyze expected runtime.

**[8:23]:** What does that mean? Uh So, we can write the recursion of this. It's T of n equals

**[8:37]:** I have two subproblems. One of them is T of K minus one. The other is T of n minus K. So, which one should I put into the recursion?

**[8:56]:** Yeah, I don't know, right? But I don't know whether my element is in on the left or on the right. So, I'll be conservative and take a max of these two.

**[9:09]:** Let me write it down a little bit.

**[9:25]:** And I have some amount of work to do before I go to the my subproblem.

**[9:33]:** What's the Yeah, what's the complexity of that of that work? Go ahead. It's O of n. Yeah, or theta n. What Why is that?

**[9:49]:** Yes, because you have to scan the array once to put the smaller elements on one side and larger elements on the other side. Now, this re- recurrence is impossible to solve cuz I don't know what K is. So, instead we'll just calculate its expectation.

**[10:19]:** So, the expectation of T of N is taking average over all the randomness, which means the choice of K. All right, so there is a probability that my K is equal to J. If my K is equal to J, then I should take the maximum of Sorry.

**[11:06]:** All right, if my K is equal to J, then I should um take the expectation of the maximum between uh putting those two.

**[11:18]:** And according to the definition of uh expectation, I should do a sum from J equals zero. No, not zero. Uh I'm starting with with one all the way to N. Right? Any questions so far?

**[11:43]:** Now, obviously uh

**[11:51]:** depending on my choice of J, sometimes this one is larger, sometimes that one is larger. All right, I'll just write it uh a little verbosely. So, if my J is one, then I should take the right one.

**[12:15]:** Plus if J J is two, then I should take N minus two, so on and so forth, right? I think that everyone's uh gets this, right? So, I'll just directly jump to the next step.

**[12:37]:** Oh.

**[12:43]:** So, when J is smaller than half of N, I will take the right one. If J is larger than half of N, I will take the left one. And they happen to be a symmetric uh uh they happen to be symmetric. And what I have here is

**[13:05]:** Everyone got that?

**[13:10]:** Mhm. Uh maybe I'm missing a minus one here. Okay, I shouldn't sum to there. Sorry.

**[13:25]:** Right? I have N minus one, N minus two, N minus three all the way to half of N. But from there, I no longer go down, right? I go backwards half of N plus one plus two plus three all the way back to uh N minus one. Any questions so far?

**[13:47]:** Oh, I we forgot our last term, which is a theta N.

**[13:56]:** Now, how do we solve this?

**[14:03]:** Any any thoughts?

**[14:09]:** This is a recurrence on the expectation of T. So, for this general this type of general recur recurrence, we don't have a a very good way. Instead, what we'll do is just take a random guess and then see if it uh if it's correct. Okay. So, I don't need to guess in this case cuz I know it's O of N. So, let's just uh assume our expectation of TN is theta of N. What does that mean again?

**[14:52]:** It means I can find some constant such that uh this expectation is bounded by a constant times N. So far so good? Now, we can use induction. Assume that this holds for everything up to N minus one, and we're going to show this uh also holds for N. Then we're done, right? Now, we'll just plug that in and the expectation of TN

**[15:34]:** will be less or equal than this sum from half of N to N.

**[15:49]:** Right? Yeah, I just plug that in. Of course plus a theta N term. Now, uh what's the sum of this guy?

**[16:05]:** Any guesses? N squared? N cubed? Or N? Okay, it's probably a little messy uh More cleanly, I can put this P out. And it's just the sigma of J. Right? If I change my sum uh decrease the range of sum by one. What is the sigma uh sum of J?

**[16:42]:** On what order first?

**[16:47]:** N squared. Okay. Yeah, definitely N squared. Uh uh We need to be a little bit more precise than that. So, what's the coefficient before the N squared?

**[17:08]:** So, I claim its coefficient is 3 over 8.

**[17:16]:** Can you guys see that? Mhm. Why why did you assume that the expected time is theta N? Oh, that's a that's just a guess. If it's wrong, we'll have to assume something else, which we will see in the next example. But good question. Okay, uh yeah, let me ask the question again. I claim this sum is roughly 3 over 8 N squared. Can anyone see that?

**[17:51]:** Any ideas?

**[17:56]:** So, I don't know how to calculate this term, but I do know how to calculate sigma from one to N. Right? This is easy, right? What's that?

**[18:12]:** It's half of N N minus one. Right? So, it's roughly

**[18:21]:** it's roughly half of N squared. Now, my this this term is the sum of this minus the sum to half of N. Right? So, it's roughly

**[18:40]:** So, it's roughly half of N squared minus 1/2 of 1/2 N squared. Make sense? So, this is roughly 3 over 8 N squared plus uh an order N term or less or constant.

**[19:05]:** Any questions? Does that make sense? Yeah. Then it's very easy if we just plug this in.

**[19:17]:** Okay. Mhm. Sorry. There is a mistake. I just realized. Can Can anyone point that out?

**[19:36]:** So, how many terms do I have in total?

**[19:42]:** One from N. We I have N term. Right? So, each term should appear twice.

**[19:52]:** Right? Yeah, so I should have a two here.

**[19:59]:** And so I somehow just throw away this probability, but this probability is uh 1/n. Right? Cuz I'm choosing a random element, there's 1/n probability that it's equal to 1 equal to 2 3 4. Everyone every of those every of this is 1/n.

**[20:27]:** Correct?

**[20:34]:** So, I should have a 2/n here. A 2/n here. And if we plug this in it's 3 over 8 n cubed plus the theta n. And our goal is to show this is less than B times n. Which is clearly true. Cuz this is 3/4 of n. 3/4 B times n. Plus another term we can we can say this is another constant D times n. And if we choose B accordingly this can hold. Any questions?

**[21:35]:** Hm? You look confused. Or too easy? Okay, I guess it's the latter.

**[21:45]:** Oh, is it not?

**[21:55]:** Okay, so then we have solved this uh expected runtime of quick find. Now let's look at quick sort. Quick sort is very similar. The only difference is that once I arrived at I once I put all the smaller elements on one side and the larger elements on the other side uh instead of going to one of them, I have to sort both.

**[22:23]:** So, the only change is that instead of taking the max here I need to add them.

**[22:35]:** Correct? So, now uh same thing here, instead of taking the max I should add them up.

**[22:50]:** Now when a public gets here so every term appears twice. All the way from n equals 1 to uh J equals 1 to J equals n. Is everyone following?

**[23:18]:** Mhm. Can you repeat that? Okay, sure. Uh originally we have a max here. Right? So, yeah, first uh did everyone get this part? We have a plus instead of max here. Like you have we have to solve both the problems. Now if it is a max, then uh what I have is n minus 1 n minus 2 all the way to half of n and then half of n half of n plus 1 all the way back to n minus 1. Right? And if I have a sum, then what I have is for the for J equals 1's case, I have T of 0 and T of n minus 1. Right? This is J equals 1. If J equals 2, I have T of 1. And T of n minus 2. Right? As J increases, this one goes from 0 to n and this one goes from n minus 1 to 0.

**[24:13]:** I'm going to sum all of them up.

**[24:23]:** Does that answer your question? Okay. So, instead of from half of n to n, we are summing from 1 to n.

**[24:35]:** Now uh we also have another good question here. Why do I guess it's theta n? Well, it's just a random guess. It could be wrong. For example, in this case it it's just incorrect. Why? Cuz every sum becomes uh the range becomes 1 to n.

**[25:02]:** Now what I have is no longer 3/8 of n. What do I have again? What do I have now if it's 1/n?

**[25:15]:** Yeah, it's 1/2 of n. But if I change 1/2 here what I get is B times n plus D times n. I'm I want to prove that it's smaller than B times n. Which is clearly impossible, no matter how you choose B.

**[25:44]:** Did everyone get that? If we make the same assumption I'll make the hypothesis and we plug them in, we can no longer prove uh the induction step.

**[25:59]:** Okay, so what do we do? We make another guess.

**[26:05]:** So, let me rewrite our recursion.

**[26:21]:** So, what's the next guess?

**[26:32]:** Any guesses?

**[26:36]:** Well, let's just guess uh How about we just guess n squared?

**[26:47]:** Okay, anyone happy with that I'm happy with that guess? So, we can do the same thing. We can plug it in. And that will be a hm sorry, I missed it another term, right? This is a 1/n or 1/2 here. If we make that guess, then what we have is a sum from

**[27:12]:** 1 to n minus 1 the sum of J squared plus the theta n.

**[27:21]:** And the sum of J squared is roughly

**[27:32]:** n cubed divided by 3.

**[27:37]:** Is that uh is is that obvious to everyone? Maybe not. Okay. Can I Can anyone explain this to us? Why can I claim the sum of square term is n n cubed over 3?

**[28:04]:** Go ahead. Mhm. It's n minus n times n minus 1 times n minus 2 over

**[28:14]:** Uh I think you are correct. There is a formula which is Yeah, I don't remember exactly, but it's roughly roughly this. Right? If you know this, then you definitely see that. If you don't this we can we can turn this sum into an integral. Right? And that is

**[28:40]:** n cubed over 3. Make sense? Now if we plug that in what do we have? 2/n 3n cubed plus theta n. Now, of course there's a B here. And we want to show this is less than B times n squared.

**[29:07]:** Does it hold? Is it true?

**[29:17]:** It's clearly true, right? So, this is Hm? No, this is cubed.

**[29:26]:** Yeah, sorry. I'm making many mistakes, but that's actually good to uh catch your attention. But it actually worries me that you didn't point this out.

**[29:39]:** Like this is 2/3 n squared times B is clearly less than B n squared. Okay, so we claim the algorithm is n squared. Correct?

**[29:57]:** Go ahead. I mean that you can claim that it's less than n squared, but you know that it's n squared definitely. Exactly. So, what I proved here is that the algorithm is definitely order n squared, but maybe less. Right? And you can see we still have a lot of room here. Right? This inequality doesn't is not very tight.

**[30:20]:** So, uh in fact, it's a very good good question. How do we make that guess? So, if this you already know the answer is n log n, right? So, it's not interesting. But, if you don't, then how do we go about and do things? We can we we have to make these guesses. So, how about we know it's n doesn't hold and two is too much. Let's guess this n raised to 1 plus epsilon.

**[30:49]:** Then what what will we have? If we carry out the same integral argument, we have 2 plus epsilon.

**[31:03]:** n raised to 2 plus epsilon over 2 plus epsilon. Correct? And if we plug that in,

**[31:19]:** we got this.

**[31:23]:** And we want to show it's less than n raised to 1 plus epsilon. Does this hold?

**[31:36]:** Right? This this term is less than one, right? And that's n raised to 1 plus epsilon. So, this is true. So, we can easily prove is indeed n raised to 1 plus epsilon and for any epsilon. Questions?

**[31:57]:** But, is it tight? We still don't know. So, then what do we do? We just make another guess.

**[32:07]:** And let's guess T of n is in order n log n.

**[32:18]:** Okay. You definitely you may run into two two cases. You can either prove it or not. If If this doesn't hold, you just go to log n squared. And gradually you will find the answer. Well, if you don't know the answer, probably this is how you do things. Now, if we guess it's n log n,

**[32:40]:** then I have a little harder equation here.

**[32:52]:** Cuz it's now j log j.

**[33:04]:** How do I compute that?

**[33:19]:** Yeah, it's not a sum of natural number or nums or squares of numbers. So, you cannot use like formula like this. But, we can still use the integral argument. Right? I'm not going to do that cuz that's what you should have learned in calculus or other math class. But, it happens that uh this integral of j log j is roughly

**[33:54]:** half of uh n squared log n minus

**[34:03]:** some constants times log n. I think you can change this constant, but it's roughly smaller uh than that. If you plug that in, you get

**[34:24]:** n over two 1 half times B. Sorry.

**[34:45]:** plus theta n and we want to we want it to be smaller than B times n log n.

**[34:56]:** Which will be true.

**[35:04]:** Right? Cuz you can Yeah, this is exactly that. And but we are minus some term. And the term we are extracting is larger than the theta n term. Okay. So, we can prove this algorithm is n log n.

**[35:23]:** But, you can ask the same question. How do I know it's n log n? Or if I don't know it's n log n, maybe I should go about and try log log n.

**[35:36]:** So, you're welcome to try. And it's actually a very good thought cuz yeah, I I think it's very uninteresting if you already know the answer. If you don't know, you have to try that. But, when do you stop? At a reasonable point, you can also prove the other way that its run time is larger than something. Here, if you we prove this big O of n log n, if you can show the other way that is omega n log n, then you know you have arrived at the final answer.

**[36:15]:** Okay. That's the math part. Any questions about that?

**[36:23]:** Yeah, any questions about everything I have said so far?

**[36:35]:** Okay. If not, uh so lastly, uh just have few comments on several terminology. Now, this uh recitation we focused on expected run time. And you have always you have already seen amortized run time.

**[36:57]:** Uh or you may have heard of average run time.

**[37:06]:** So, to be honest, expected and amortized are just two fancier ways of saying average. But, uh in algorithm analysis, we do mean slightly different things uh with these terms.

**[37:25]:** So, the difference uh is that we are averaging over different things. So, if we say average run time, we usually mean taking the average over input. Right? We can imagine a quick sort or quick find algorithm that doesn't use randomness where you always select your first element as your pivot. That's a reasonable algorithm. If your input is random, then you can carry out the same argument and show that its complexity is of n or of n log n. But, if your input is pre-sorted or reverse sorted in some special cases, you cannot do that. So, average run time is usually a very weak argument cuz you have to make assumptions about uh your input. And expected run time uh is definitely better because we are taking average over the randomness we introduced. It's in They are independent of the input. So, we are not making any assumptions uh on the input.

**[38:25]:** So, of course, this comes at a price. This randomness doesn't come for free. So, in fact, it's very hard to generate high quantity random numbers. And maybe at the end of the class you will see that in crypto um a lot of the a lot of works are just devoted to generate high quantity random numbers. If you can do that efficiently, you actually solve a lot of problems. So, amortized run time are slightly again different from these two cuz they are taking average over the number of operations. Right? It's you're doing many many operations in a row and some of them takes longer, some of them take shorter, and you take the average on those.

**[39:09]:** Okay. That's today's recitation. Any questions?

**[39:20]:** Okay.
