First of all, when we select it pivot the random pivot which is not in

their sub range, and then all the elements from this sub range in this

sort of element goes either to the left or this to the right.

So, they all stay together in the same branch of three, okay.

So before we select a pivot which stays inside this range,

all these elements stay together in the same sub-array.

Now, assume that we selected a pivot from this sub-range, and

assume that it is not A'[i] or A'[j], for example.

In this case a prime of A and a prime of J will be splitted apart.

They will go into different parts with respect to this pivot, right?

At this point I must humor that all the elements in my summary are different,

and in duality are different, okay?

So once again, if the first selected element

from this subrange is not prime of A or

a prime of j then these two elements are not going to be compared.

Because right after the partition procedure uses this pivot

from this range A prime of a and A prime of j will go to different parts, right?

If, on the other hand, the first selected

pivot from this subrange is either A prime of a or A prime of j,

then these two elements are going to become paired, right?

So this is the most important observation in this proof.

Everything else is just calculations.

So if this is clear, let's then estimate

the probability that second respondent to elements are compared.

So we know that they're compared if and

only if the first selected Pivot in this sub range is one of these two elements.

This helps us to estimate the probability of