For randomized quicksort sorting method running on input arr

For randomized quicksort sorting method running on input array <6, 5, 1, 3, 2 , 4>, what is the probability that 1 & 3 will be compared during a call to Partition? What is the probability that 4 & 5 will be compared?

Solution

For any two random variables X and Y , E[X+Y ] = E[X] + E[Y ]. Proof (for discrete RVs): This follows directly from the definition.

E[X + Y ] = X eS Pr(e)(X(e) + Y (e)) = X eS Pr(e)X(e) + X eS Pr(e)Y (e) = E[X] + E[Y ].