Que – Consider the recursive quicksort algorithm with “random pivoting”. That is, in each recursive call, a pivot is chosen uniformly at random from the sub-array being sorted. When this randomized algorithm is applied to an array of size n all whose elements are distinct, what is the probability that the smallest and the $2^{nd}$ largest elements in the array are compared during a run of the algorithm?
I am getting – $\frac{2}{n}+(\frac{1}{n}*\frac{2}{n-1}) = \frac{2}{n-1} $
Please verify.
