Transcript
Good morning, everybody. How's everybody doing? Nice long weekend we just came from. I'm doing well. I'm actually getting over a little cold. Uh aw, yeah, unfortunately. Uh but uh after this I I don't have anything else this week, so that's good. Um okay, so last time, last week, we talked about how uh we looked at the uh search problem that we talked about uh earlier that week and showed that in a certain model of computation where I kind of could only compare two objects that I'm storing in my that I'm storing and get some constant number of outputs on what I could how I could identify these things, like equal or less than or something like that, then we drew a decision tree and we got this this bound that if I had n outputs, right?
I would require my decision tree to be at least log n height. And so in this model I can't find the things in faster than log n time. But luckily, we are in a uh model of computation which has a stronger operation, namely random accessing. And if we stored uh the things that we were looking for, that we we have unique keys and those keys are integers, then if I have an item with key K, I if I store it at index K in my array, then I can find it and manipulate it in constant time, right? That's pretty cool. That's what we called the direct access array. A direct access array really not different than a regular array, except how we're you're using it when we were talking about sequences is we were giving kind of extrinsic semantics to the slots where we were storing these things.
Basically, I could put any item in any slot, right? Where it was in my array had nothing to do with what those things were. Here, we are put imposing intrinsic semantics on my array that if I have an item with key K, it must be at index K, right? That's That's the the thing that we're taking advantage of here, and then we can use this nice powerful linear branching random access operation to find that thing in constant time because that's our model of computation. Okay. Then, what was the problem with this direct access array? Anyone shout it out? Space. Right. So, we had to instantiate a direct access array that was the size of the space of our keys, right?
In general, my index location is could go from zero to some positive number, right? If I have very large positive numbers, if I was sorting if I was searching among your MIT IDs, I'd have to have a direct access array that was that spanned that space of possible keys you could have, right? And that could be much larger than n. And so the rest of the time we talked about how to fix that space problem. We can reduce the space by taking that larger key space from zero to U, which could be very large, and map it down to a small space. Now, in general, if I give you a fixed hash function there, that's not going to be good in for all inputs.
If your inputs are, you know, very well distributed over over the key space, then it is good, but in general, there would be hash functions with some inputs that will be bad, right? That's what we kind of argued. And so for the the rest of the time there, we we talked about hash families, choosing a hash function randomly from among a a large set of hash functions, which had a property that if I chose this thing randomly and you generating your input didn't know which random numbers I was picking, the expectation over my random choice, me, I'm the one running the algorithm, not you giving me the input, that random choice, my algorithm actually behaves really well in expectation.
In particular, I got constant time for finding, inserting, and deleting into this data structure in expectation. We did a little proof of of of that the chain lengths where we stored collisions in our hash function in our hash table, sorry. Those wouldn't be very long, and so if they were constant, then I don't have to search more than a constant number of things when I go to an index a hashed index location. Does everyone remember what we talked about last week? And we then uh I didn't show you this chart at the end, uh but I'm showing it to you now. Essentially, what we had was we have a bunch of different ways to deal with this set interface.
And last week, we talked about the sorted array, and then we talked about this direct access array and this hash table, right? Which do better for these uh uh dictionary, the find and insert and delete operations, or at least better in an expected sense, right? What's the worst case performance of a hash table? If I have to look up something in a hash table and I happen to choose a bad hash table hash function, what's the worst case here? What? N, right? It's worse than a sorted array, right? Because potentially I hashed everything that I was storing to the same index in my hash table, and and to be able to distinguish between them, I can't do anything more than a linear search, right?
I mean, I could store a another set data structure as my chain and do better that way. That's actually how Java does it. They store uh data structure we're going to be talking about next week as the chains so that they can get worst case log n, but uh in general, uh that hash table is only good if we're allowing Okay, I I want this to be expected good, but in the worst case, if I really need that operation to be worst case, right? I really can't afford linear time ever for an operation of that kind, then I don't want to use a hash table. And so on your Pset 2, everything we ask you for is worst case, so probably you don't want to be using hash tables, right?
Okay. Yes. What does the subscript E mean? That's great. In this chart, uh I put in a subscript on this is an expected runtime, right? Or an A meaning this is an amortized runtime. At the end, we talked about how if we had too many things in our hash table, then as long as we didn't do it too often, right? This is a little hand-wavy argument, but the same kinds of ideas as the dynamic array, if whenever we got a linear uh we were we were more than a linear factor away from where we were trying what uh basically the fill factor we were trying to be, then we could just completely rebuild the hash table with a new hash function randomly chosen from our hash table with a new size, and we could get amortized bounds.
And so that's what Python how a Python implements dictionaries or sets or even objects when when it's trying to map keys to different things. Uh so that's hash tables. That's great. The key thing here is, well, actually, if your range of keys is small, or if you as a programmer have the ability to choose the keys that you identify your objects with, you can actually choose that range to be small, to be linear, to be small with respect to your items, and you don't need a hash table. You can just use a direct access array, right? Because if you know your key space is small, that's great. So a lot of C programmers probably would like to do something like that.
Because they don't have access to Maybe C++ programmers would have access to their hash table. Any questions on this stuff before we move on? Yeah. Why is it expected, right? When I'm building, I could insert I'm inserting these things from X one by one into my hash table. Each of those insert operations, I potentially have I'm looking up to see whether that an item with that key already exists in my hash table, and so I have to look down a chain to see where it is. However, if I happen to know that all of my keys are unique in my input, right? All the items I'm trying to store are unique, then I don't have to do that check and I can get worst case linear time.
Is that Does that make sense? All right. This is a subtlety, but that's a great question. Okay. So, uh today, instead of talking about searching, we're talking about sorting. Okay? Last week, we saw a few ways to do sort. Some of them were quadratic insertion sort and selection sort. And then we had one that was n log n. And this this thing n log n seemed pretty good, but can I do better? Right? Can I do better? Well, what we're going to show at the beginning of this class is in this comparison model, no. n log n is optimal. And we're going to go through the exact same line of reasoning that we had last week.
So, in the comparison model, what did we use when we were trying to make this argument that any comparison model algorithm was going to take at least log n time. What we did was we said, "Okay, I can think of any model in the comparison model uh any algorithm in the comparison model as kind of this some comparisons happen. They branch in a binary sense, but you could have it generalized to any constant branching factor, but for our our purposes binary is fine. And what we said was that there were at least n outputs. Really n plus 1, but you know, at least order n outputs. And we showed that or we argued to you that the height of this tree had to be at least log n.
Right? Log the number of leaves. It had to be at least log the number of leaves. That was the height of the decision tree. And if this decision tree represented a a search algorithm, I had to walk down and perform these comparisons in order, reach a leaf where I would output something. So, I I need if if the minimum height of any binary tree on a linear number of leaves is log n, then any algorithm in the comparison model also has to take log n time because it has to do that many comparisons to differentiate between all possible outputs. Does that make sense? All right. So, in the sort problem, how many possible outputs are there?
What is the output of a sorting algorithm? What? What's up? A list. In particular, given my input, right, like some set of uh items A that has size n, right? What I'm going to give you is some permutation of that list, right? So, for each index, say, I could tell you where it goes. Right? Another way I could say is where does the first item go to? Where does the second item go to? Where does the third item go to? Blah blah blah like that, right? So, how many different choices of a permutation are there? Well, how many choices do I have for the first thing of where it could be in the final sorted array?
It could be in any of the places, right? So, it's n. How about this one? The second one? Well, it can't go to where this one went, right? But it can go anywhere else, so it's n minus 1. And since these are independent choices I'm making, if I multiply them all together, I get n factorial permutations that are the number of possible outputs that I have to my sorting algorithm, right? So, for me to have an output to my sorting algorithm be correct, I need at least n factorial leaves. Does that make sense? Okay. The nice thing about doing this last week is this is really just the number of leaves.
And this is really the number of leaves, right? So, what's the number of leaves? It's theta n factorial. Here it's actually n factorial, but I'm just going to put it there. And here, we get an n factorial. I think this is I see. So, it's at least omega n factorial. Does that make you happier? Theta here. Thank you. Has to be at least. So, this was right. Okay. So, at least this many I I could there are there are algorithms that if it got to it could take two different routes to get to the same output, right? So, this is a lower bound on the number of leaves. Okay? So, what this argument is saying is that if I just replace the number of leaves n here with n factorial, I get a similar comparison sort lower bound now.
So, what is log of n factorial? This is familiar from pset one, maybe. So, one thing I could do is I could put in Stirling formula, right? And that'll give me something of the form n log n. But what's another way I could lower bound n factorial? Well, I have a bunch of things here that's n factorial. Half of these things, these half, n over two things, are bigger than or equal to n over two. Does that make sense? So, I can certainly lower bound this thing by n over two to the n over two. That's a little easier thing to take a log of, right? If you take a log of that, that's asymptotically n log n.
So, what we're getting here is any sorting algorithm here takes at least n log n comparisons. And so, merge sort's the best we can do. Okay? Does that make sense to everybody? We're just piggybacking on the analysis we had about decision trees, connecting leaves with the minimum height of any binary tree on that number of leaves, and just replacing n with n factorial. Nothing super interesting here. Yeah? Yeah, sure. You can just plug in Stirling formula, but I I did this, so I might as well clarify. There are n terms here in the product, right? Half of them are at least n over two. Does that make sense?
So, I can replace I can lower bound this product by something smaller than half of the terms, a product of that, and that'll be fine. Right? So, I'm taking n over two of them, and I'm multiplying n over two all together, n over two times. Does that make sense? Okay. It's just providing a lower bound, right? I just need something that's smaller than all of these terms, and multiply them all together, and that'll give me a lower bound. Okay. So, we can't do better than n log n in the comparison model. But what we did last week was use random access and a direct access array to do better. Okay? So, how can anyone think of how to use that idea to sort faster?
And I'm going to give you a caveat here. I'm going to let you assume that the keys of the things you're trying to sort are unique. Okay? And say they're in a bound in a small range. So, how could I use a direct access array to sort faster? Any ideas? Yeah. Uh-huh. Okay. So, what your colleague is saying is exactly correct. It's something that I like to call direct access array sort. We won't really call it that because there's something more general that we'll uh talk about in just a second. But what your colleague was saying is instantiate a big direct access array. Direct access array sort, right?
I'm instantiating this big direct access array of the the space of my keys, right? And what your colleague was saying was I take each one of the items in my the things that I'm trying to sort, I look at each one of their keys, and I stick it in the direct access array exactly where it needs to go. Right? In constant time. That's great. Now, I gave you this caveat that all the keys were unique, so I don't have to deal with collisions here, right? But then after I'm done with this, all of these things are now in sorted order. And what I can do is I can just walk down this list. A lot of these cells are empty, potentially, right?
Well, some of the keys might not be there. But what I can do is just walk down this list, pick off every item that does exist, stick them in an array, I'm done. Right? So, what's the uh stick a key into here, and then So, all right. Uh make direct access array. Store items uh item X in index X.key. Uh walk down direct access array and return items seen in order. Does that make sense to everybody? All right. How long does this step take? Building a direct access array order U. Okay, so this is order U. How long does this take? How many items do I have to insert? Order N I or just N. And how long does it take to insert each one of these things into my direct access array?
Worst case constant time. Right? So, this is N times worst case constant time. Great. How long does this last one take? Anyone? O of U also, right? Because I'm walking down the entire length of U. So, this algorithm takes in total N plus U time. This is great. If U U is bigger than N because we assume to distinct keys, right? But, if U is on the order of N, then we now have linear time sorting algorithm. Yes. What's up? I'm sorry, you have to speak up. Uh how do I attach keys to my inputs in my So, uh in for set data structure that we've been talking about, all of my items have keys. That's just something that we impose on our input.
Each of the keys is in this case it has to be a number. Right? So, it's a That's a nice point, right? We do this to uh kind of talk about sorting items generally so that uh we don't have to deal with potentially if these keys have values associated with or other stuff associated with you can put them on that item and they'll still be there. But, in general, if you just wanted to sort integers, you could say that dot key is points back to the object itself if you want to just sort some integers. Does that make sense? It's a good question though. Okay. So, that gives us a linear time algorithm when U is small, right?
And under this condition that I have unique keys when I want to sort. Right? Those are fairly restrictive, so we might want to generalize this a little bit. Okay? So, that's direct access array sort. What if we had a set of keys that was a little larger? Right? Instead of enforcing So, let's say U is theta N implies implies linear time sorting. That's great, okay? So, now what happens if we expand that range a little bit? Say U is less than or equal to N squared, maybe just less than. Okay? Okay, this is a bigger range. Right? And if we instantiated a direct access array of quadratic size we'd have a quadratic time algorithm.
This is not helpful. Right? Anyone have a way in which we could sort integers that are between 0 and N squared? Maybe using the stuff that we had above. Yeah. Ah, your colleague is saying exactly the thing that I'm looking for, which is great. Which is maybe we could break this larger number into two smaller numbers. Right? Any uh integer that is between 0 and N squared can be written as uh key can be some A and B where A is essentially the higher kind of uh N and B is kind of the lower N. This is kind of weird. Okay, so what do I actually mean by this? I mean that let's let A be K when I divide it by N integer, the floor, right?
Key integer divide by N. Right? And B equals K mod N. So, this is a number that's less than N and this is a number that's less than N. Does that make sense? And actually, I can recover K at any time by saying K equals A N plus B. I've essentially decomposed this into a base N representation of this number. And I have two digits in that number. This is the kind of nth N digit and this is the ones digit. Does that make sense? All right. So, now let's say I have this list of numbers. Um 17 3 24 22 12 How I could Here I have five numbers. So, what's N in this case? Five. Okay. Not so interesting. N is five here.
And I'm going to represent this as five pairs of numbers that are each within the bounds of zero to four, right? Does that make sense? So, what is my AB representation of 17? Three two. Okay. So, yeah, so there are three times five plus two. That's good. That's 17. Yeah? I think I Your colleague did that right. Uh I have all of these written down, so I'm just going to write it out. And I hope I did it correctly. Okay. 3 2 0 3 4 4 4 2 2 2. Okay. So, now I have a bunch of things that I want to sort based on this function that I have, right? These are no longer just integers that I need to sort. I need to sort by this transformation of this thing into a number.
Does that make sense? So, anyone have any ideas on how we could sort By the way, these are both in uh constant time operations on your computer as long as it's an integer division, right? And this is mod. Python also has a nice thing I think in uh in its uh standard operations, which is divmod of KN, is that right? Yeah. So, if you want to use that, you can. Okay, so how do we sort these tuples? These are tuples, right? You guys are I'm sure very familiar with tuples by now. Okay. How do I sort these tuples? What's the most important digit of this thing? If I had to sort one of the digits and get something that's close to sorted what's more important, the ones digit or the N's digit?
And Okay, we have a discrepancy here. Who says one? Who says N? Someone who said N, tell me why. Oh, you all think that way for no reason. Yeah. Sorry, this is a little confusing. This is the ones digit. This is the ends digit. This is the ends digit. This is the ones digit in how I'm writing this. Does that make sense? Yeah. Exactly. Yeah, so what your what you're calling is saying is exactly correct. I could very be all I want, right? With the same A. If I change A by one, it doesn't matter what B is, it's going to be bigger, right? Does that that make sense, right? The the K is much more sensitive to A than it is to B.
Right? So, A is more important than B. Does that make sense? So, if I just want to get some linear time algorithm, I could just sort by their bigger digits and hope they don't don't differ very much on the smaller things. I've kind of sorted these things. Does that make sense? Okay, what if I actually want to sort these things? Any hints? Yeah. I need to I need to sort on both in some sense. In particular, I like to think of what I'm going to tell you right now is is uh an algorithm that I like to call tuple sort, but you can also think of it as like Excel spreadsheet sort, right? I have an Excel spreadsheet of a bunch of data.
I have a prioritization on how important the keys are to me, the columns, right? And if I have a very important column, and and an order of the columns of how how important they are to me, I can repeatedly sort on the columns until they're sorted based on my preference. That's something that you may have done. Now, if I have an ordering on the preferences of my columns, do I start by sorting all of them on the most important thing or the least important thing? What? Who says most? Who says least? There's discrepancy here. All right. Let's try it out. All right, tuple sort. Let's start by sorting these things by least significant first and then No, most significant first and then least significant.
That was the first thing I asked you, right? All right, so these are the most significant things, the first ones, and these are the less significant things. All right, instead of writing it as tuples, I'm going to write them as 32 03 44 42 22. Is everyone cool with that? This is just base five representation, okay? All right, so let's start by sorting all of these things by the most significant thing, right? Which is by this guy, this guy, this guy, this guy, and this guy. Okay, so how do I do it? The first one is 03. Second one is 22. The next one is 32. Uh 42. And then 44. Maybe 44. I don't know.
Does it matter? The order in which I put these things? I don't know. I'm just going to keep it the same order for now. All right, so I've sorted it by the least significant or the most significant. Sorry, the leading term. And now I'm going to sort by the least significant. So, what's the least significant here? 22. Then two is also This is also two. This is also two. This is three. And sorted list, voila. Why did that not work? Yeah. Yeah, so what happened is I did take into account the significant digit sort, but when I did the less significant thing, it erased all of my work from up here. Does that make sense?
In the case of ties, we want the more significant thing to take precedence. So, we want to do that thing last. Does that make sense? So, the right way to do this This is uh most significant first. Add. Okay, not good. All right, least significant first. Let's try that. Uh so, least significant here is two. Okay, so I see a uh a 32 42 22 03 and then 44. Okay? Sound good? Least significant first. Now I do most significant. I sort the most significant thing. Okay, so what's the most significant thing? 03. 22. 32. Uh most significant four 44 and 42. Cool. We're sorted, right? I did what you told me to do.
I sorted by the most significant thing. What's What's the problem here? What did I do wrong? You wanted me to put 42 here and 44 here, right? Because 42 came first in the input and 44 came second, right? Okay, if a sorting algorithm maintains this property that if they have the they have the same thing, right? Then the output maintains their order from the input to the output, their relative order. That's what we call a stable sorting algorithm, right? And so, if we have a stable sorting algorithm when we're doing tuple sort, when we're uh sorting on different keys or columns of a set, right? We really want to be using a stable sorting algorithm.
Does that make sense? Because otherwise, we may mess up work we did before in a previous sort of the less significant things. And so, yes, we want a stable sorting algorithm here. Because then we will end up sorting our thing. Does that make sense? Yes. Uh so, what your uh uh colleague is saying, let's sort by most significant, then look at all of the things with one of those that that are the same, and now sort that. That's something we could do. Okay, how long would that take? Well, let's say I didn't use half of my more significant set of digits, right? Say I'm only using n over two. Or that's not quite quite going to get what I want.
Say Say again? Yeah, so what we're going to do if we have direct access array sort, if I then go into each one of these digits and try to sort the things that are in there, that's going to take time, right? It's going to take time per each of those digits. Now, each There might be at at uh a ton of collisions into one of the things, and so I might take more time to sort that than linear. Does that make sense? So, I would prefer to do this tuple sort kind of behavior, sorting the smaller thing, sorting the bigger thing, and because I only have a constant number of things in my tuples, this is important, because I only have two things I'm worried about here, I only have to do two passes of a sorting algorithm to be able to sort these numbers.
However, can I use direct access array sort here? What was the initial stipulation I had on direct access array? That the keys were unique. That's exactly the opposite of what we have here. We have things that could be the same. So, we give up. Can't do it. What do we do instead? We Yeah? You've already said the thing that I'm looking for, so that's great. Your your colleague said, "Why can't we just put more things at a key?" Right? Why can't we put a list there? That's exactly what we do. This is called counting sort. And what we do here is we still have this direct access array of space U minus zero to U minus one, but instead of have storing one thing here at each key K we store a pointer to a chain.
This sounds like hashing, right? But the important thing is that I need to make sure as I'm inserting things in here that I'm maintaining the order in which they came in, right? I can't just throw them willy-nilly, or else we have this problem up here that we had before. Right? So, I need what I would say is a sequence data structure, right? Something that will maintain the order that I the extrinsic order that I had when I'm putting these things in, right? So, as I have multiple things with K right? I'm going to put them in the order I can basically I can put have a pointer to a dynamic array or a linked list where I just add things to the end.
And then at the end of my algorithm when I read off the things I can just look at anyone that has a non-empty data structure under here and read them off in the order that they came. Does that make sense? So, for this example uh I'm just going to do this last step here from the first row to the second row. I'm going to have this direct access array with 0 1 2 3 4 on the slots. Right? So, how am I going to do this counting sort now? I have 32 42 22 03 and 44. I'm going to take the first one, 32. I'm sorting by the most significant thing. I stick it here. 32 and then 42 4. Okay, 42. Sorry, 42. 22 All right.
This is not so much different yet than dynamic array I I'm uh direct access array sort, but when we get to this duplicate uh right, 44 here we now have two things in this thing, and because we are keeping them in order in this sequence I'm appending to the end then when I go and read off the different things then I'm returning them in a stable way in the way that I I want them to be. Does that make sense? And it's not overwriting the work I did on the lower significant digits. Okay? So, how long does this take? This also only takes order N plus U because I'm instantiating this thing of size U and then how big are these data structures?
Well, maybe I'm storing one a constant amount for each index, so that's a U overhead, and then I'm paying one for every item I'm storing. Right? These things are only the lengths the the sum total of their lengths is N, right? Cuz I'm only storing N things in there. So the total amount of space, the total amount of work I have to do is order I need to have be able to append in constant time and I need to be able to cycle through these things, iterate over them in linear time, but if I have that I get N plus U. Yeah. Uh so, your uh your colleague is saying, "How do I ensure that the things in these lists that where they collide, how do you ensure that they're sorted?" I don't.
I just ensure that they came in in the order that they came, right? But as long as I sorted the lower order digits correctly in the previous things then I'm assuming that their order as they come in will be sorted if they collide. That's the assumption. That's the reason why I'm doing these building up from the least significant to the most significant. It's so that I know that when they collide the underlying stuff there is sorted already in the input. Does that make sense? Great. Yeah. So, this one is still I'm using a direct access array on the keys though. This is N. This is N because I chose uh so, counting sort is general for any U.
I just happen to pick U being N in this case when I broke this thing up into N squared, but this general concept is it uh it doesn't matter what I choose for U. Does that make sense? Okay, but we will use that right now to sort larger ranges of numbers. Okay? So the idea here this was exactly the idea. We're going to combine tuple sort use counting sort as its auxiliary sorting stable sorting algorithm right? To do all its work on these digits, right? And so to sort on N squared size numbers I get linear time, which is great, right? Because U is N in this case. Okay? So but can I extend that? What if I had N cubed?
What if I had up to size U equals N cubed or less than N cubed? How many digits would I have there? How many size N digits would I need to represent a number of size N cubed? Any ideas? What did we do here? We divided off an N. We took it and stored it. We're left with something of size N, right? If I had a number of size N cubed, I could divide off an N, I'm left with something of N squared. I don't know how to deal with something of N squared. Actually, I do. I can split it up into two size N numbers, right? So, if I had numbers bound upper bounded by a a cubic, right? N cubed, I could split it up into three digits.
Three is still constant, right? And so, I could split it up into three digits, tuple sort them in their increasing priority and sort those. Again, I'm doing linear work per digit. I have a constant number of digits, so I get a linear time algorithm. Yeah? Uh-huh. Yeah, so it's always going to be big O of N plus U but because I'm bounding my digit size to be N U is N there and so, I'm getting linear time. Does that make sense? Yeah. So, the idea here, this is what we call radix sort. Radix sort. Break up integers uh max size U into a uh a base N tuple. Right? So, basically each one of my digits can range from zero to N, right?
How many digits do I have if I have How many base N digits do I have if I have a number of size U? Yeah, log N of U. Number of digits is log N of U. Log base N of U, right? So, how long does ray and then tuple sort on digits using counting sort? From least to most significant. Right? That's the algorithm. How long does that take? How long does it take to sort on a digit that spans the keys zero to N? Linear time, right? Order N time. How many times do I have to do this tuple sort? The number of digits times, right? So, the running time of this algorithm first I have to you know I have to do this stuff, break up each of the integers, that takes N time, right?
N times the number of digits. I had to create each one of these uh tuples, right? So, n plus n times the number of digits, right? log log base n of u. Right? So, here I had to loop through all the things. And then here for each thing I broke it up into log base n of u digits. And that's how long the first thing took. And then how long did it take me to tuple sort? n time per digit. So, I also get this factor. Does that make sense? So, how long did How long is that? Is that good? Is that bad? For what values of u is this linear time? If u is less than n to the c for some constant c then this c comes out of the logarithm.
log n of n is one. And we get a linear time algorithm. Does that make sense? Okay. So, that's how we can sort in linear time if our things are only polynomially large. Right? So, in counting sort we get n plus u. In radix sort we get also a stable sorting algorithm where the running time is n plus n times log base n of u. Does that make sense? And then in the situations where uh there's a typo there in counting sort. That should be when u is order n. Counting sort runs in linear time. And it's linear time also in the case of radix sort if our things are bounded by a polynomial in n, right? By n to the c for some constant c.
Does that make sense? All right. So, that's how to sort in linear time with the caveat that your numbers aren't too big. Okay. See you next week.