Okay, so this is going to be an important definition in our analysis.
It's important you understand it.
So, for something like the third smallest element and the seventh smallest element.
xij is asking, that's when i equals 3 and j equals 7, x37 is asking
how many times those two elements get compared as QuickSort proceeds.
And this is a random variable in the sense that if the pivot choices
are all predetermined, if we think of those being chosen in advance.
Then there's just some fixed deterministic number of times that zi and
zj get compared.
So it's important you understand these random variables xij, so
the next quiz is going to ask a basic question about the range of values
that a given xij can take on.
So for this quiz we're considering as usual some fixed input array.
And now furthermore fixed to specific elements of the input array.
For example, the third smallest element,
wherever it may lie, and the seventh smallest element, wherever it may lie.
Think about just these pair of two elements.
What is the range of values that the corresponding random variable
xij can take on?
That is what are the different number of times that a given pair of elements might
be conceivably get compared in the execution of the QuickSort algorithm?
All right, so the correct answer to this quiz is the second option.
This is not a trivial quiz.
This is a little tricky to see.
So the assertion is that a given pair of elements,
they might not be compared at all.
They might be compared once and they're not going to get compared more than once.
So here what I'm going to discuss is why it's not possible for
a given pair of elements to be compared twice during the execution of QuickSort.
It'll be clear later on, if it's not already clear now, that both 0 and
1 are legitimate possibilities.
A pair of elements might never get compared and they might get compared once.
And again, we'll go into more detail on that in the next video.
But why is it impossible to be compared twice?
Well think about two elements, say the third element and the seventh element.
And let's recall how the partition subroutine works.
Observe that in QuickSort, the only place in the code
where comparisons between pairs of input array elements happens.
It only happens in the partition subroutine, so
that's where we have to drill down.
So what are the comparisons that get made in the partition subroutine?
Well, go back and look at that code.
The pivot element is compared to each other element in
the input array exactly once.
So the pivot just hangs up in the first entry of the array.
We have this for loop, this index j which marches over the rest of the array.
And for each value of j,
the jth element of the input array gets compared to the pivot.
So summarizing, in an invocation of partition,
every single comparison involves the pivot element.
So two elements get compared if and only if one is the pivot.
All right so let's go back to the question.
Why can't a given pair of elements of the input array get compared two or
more times?
Well, think about the first time they ever get compared in QuickSort.