What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element? Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this randomized algorithm is being applied to an array with n distinct element, what is the probability that the smallest and the greatest element will be compared during run of the algorithm.
It is $2/N$ : the probability of picking the smallest or the biggest as pivot.
If you choose one of them, they will be compared.
If you choose any other, then the smallest and the biggest elements will be put in different partitions, and thus will not be compared.