# In a sorted subarray $Z_{ij}$ elements $i$ and $j$ get compared when either $i$ or $j$ is pivot

This is related to the discussion of average case of quick sort. Given that we have a sorted sub-array $$Z_{ij} = i, i+1, \dots, j$$ where $$i < j$$.

Claim: $$i$$ and $$j$$ are compared if and only if, among all elements in $$Z_{ij}$$, the first element to be picked as a pivot is either $$i$$ or $$j$$.

Forward direction Proof: The “only if”: suppose the first one picked as pivot is some $$k$$ that is between $$i$$ and $$j$$, then $$i$$ and $$j$$ will be separated into different partitions and will never meet each other.

Problem 1: For backward direction above, I understand that it should be that if the first element to be picked as a pivot is either $$i$$ or $$j$$, then $$i$$ and $$j$$ are compared. So I am not sure why the "only if" part was stated as above please?

Backward direction Proof: The “if”: if $$i$$ is chosen as pivot (the first one among $$Z_{ij}$$), then $$j$$ will be compared to pivot $$i$$ for sure, because nobody could have possibly separated them yet!

Then we can proceed and define $$X$$ to be the total number of comparisons and so on until we have $$O(n\log{n})$$ complexity, which is clear once the above claim is understood, which I have some issues with please.

If $$i$$ that is chosen as a pivot guarantees based on the proof that we will get $$O(n\log n)$$ complexity based on the condition that $$i$$ is the first element to be a pivot and $$j$$ to be after $$i$$, then we can see that $$E[X_{ij}] = \Pr(i \text{ or } j)$$, where $$\Pr$$ back means the probability that either $$i$$ or $$j$$ to be the first pivot and both at the beginning and at the end of the array.

$$E[X] = \Sigma_{i}\Sigma_{j=i+1}E[X_{ij}] = \frac{2}{j-1+1}$$

Claim 2: Now in the randomized case, we can assume a less clever assumption (which I don't understand) that: Given that $$n$$ is the number of elements to be sorted and $$T(n)$$ is expected time to sort $$n$$ elements. First pivot chooses $$i$$th smallest element, all equally likely. Then:

$$T(n) = (n-1) + \frac 1n \sum_{i=0}^{n-1}(T(i)+T(n-i-1))$$ $$= (n-1) + \frac 2n \sum_{i=1}^{n-1}(T(i))$$

Problem 2: how the previous claim is less clever than the first one please? And how $$T(n)$$ above is formulated?

Problem 3: how $$T(n)$$ becomes $$T(n)= (n-1) + \frac 2n \sum_{i=1}^{n-1}(T(i))$$

• Problem 2 is unanswerable – which claim is more clever is completely subjective. Oct 2 '21 at 10:57
• Problem 3 you can solve on your own. Try harder. Oct 2 '21 at 10:57

The claim is proved as follows (in reverse order):

• If the first element among $$Z_{ij}$$ to be chosen as pivot is $$i$$ or $$j$$, then $$i$$ and $$j$$ are compared.
• If the first element among $$Z_{ij}$$ to be chosen as pivot is not $$i$$ or $$j$$, then $$i$$ and $$j$$ are not compared.

The forward direction is the contrapositive of the "only if" implication.

Being clever or not is subjective rather than technical. I would just ignore this designation.

$$T(0) + T(n-1) + T(1) + T(n-2) + \cdots + T(n-1) + T(0) = 2(T(0) + T(1) + \cdots + T(n-1)).$$
• Thank you very much. I see that $T(0) + T(n-1), ...T(n-1)+T(0)$, so have 2 of each and thus we got 2 multiplied by sum please? If this is true, so this "less clever" approach is basically assumin pivot can be any element and thus $T(i) + T(n-i-1)$ please?