[MUSIC]

So we've worked through this example and now we really understand the task at hand.

And so it's good before we do the solution to just

reaffirm what the assumptions that we're making are.

And at this point, we know that our array is given to us without

any information about how it's organized and it may have some duplicate elements.

But we're allowed to change the array as we proceed with the algorithm.

And so, we're looking for the kth smallest element.

And what we might want to do is build up to the kth smallest element by looking for

the smallest element and then the next smallest element and then the next

smallest element after that and then keep on going until we've gone to the kth one.

We notice that that's somewhat similar to the procedure that we have to do for

selection sort.

And with selection sort, we find the smallest element and

we swap that to a first position of the array so

that we can think about ignoring it afterwards or discarding it in some sense.

And then we focus on the rest of the list and find

the smallest element among those remaining elements, swap that to the beginning, and

then just keep on focusing on the remaining elements.

And this would give us an algorithm that's a variant

of selection sort that we already know.

And so it's always nice when we can use our previous knowledge to inform design of

future algorithms.

But before we go ahead and code this solution,

let's analyze it to see if it's worth coding.

Because it was just our first hunch at how we might solve this problem.

And so it's good to stop and think and

evaluate before we go further any one direction.

And so if we evaluate the performance of this approach, what we're doing at each

point is finding the minimum element of an array of numbers.

And if we wanted to find the minimum amongst an array of elements,

what we have to do is look at each one of those elements.

And that takes linear time.

And so even though the number of elements that we're considering each time decreases

by one, we still might be doing this, we still are doing this k many times.

And so, for really small k, if we just need to find the very smallest element or

the second smallest element, in that situation,

this would give a linear algorithm.

But in the more general situation, where k maybe is n/ 2,

and we're finding the element that is right in the middle, the median,

then if we have to do this approach, say n/2 many times or

any O(n)many times, then all of a sudden our algorithm becomes quadratic.

And that's a problem.

Because quadratic algorithms, they're kind of slow,

especially if our problem has something to do with sorting.

And so we've already seen how the algorithm that were devising is related

to sorting, in the sense that it's related to the selection sort algorithm.

And so maybe we can use that insight to come up with a better solution.

And so what if we sorted the array before doing anything

in terms of finding the kth element?

And as a preprocessing step, let's just apply our favorite sorting algorithm and

organize all the elements from smallest to biggest.

And the advantage of doing that is that, at this point, the element that we care

about, the kth smallest element, is in position k in the array.

And accessing an element in a particular position in the array

is a constant time operation.

So overall, we've now come up with an algorithm that takes

however long a sorting takes for the preprocessing step.

And then O(1) time for

the second step which is retrieving that kth smallest element.

And the advantage of having these two separate steps is that sorting

is a really well studied problem and we know that in the worst case there

are still algorithms out there that solve sorting with n log n time.