The Gateway to Computer Science Excellence

+1 vote

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.

0

I think it will be.

among the N elements, we have to choose either the smallest element or 2nd largest element.

So, $\frac{1}{n} + \frac{1}{n}*\frac{1}{n-1} = \frac{1}{n-1}$ .

Am I right ??

0

@kumar.dilip Acc. to me, those 2 elements are compared only when-

Case 1 - Any of them is chosen as a pivot during $1^{st}$ split.

Case 2- Largest element is chosen as a pivot during $1^{st}$ split and smallest or $2^{nd}$ largest element is chosen as a pivot during $2^{nd}$ split.

52,345 questions

60,501 answers

201,871 comments

95,325 users