+1 vote
272 views

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}$

| 272 views
0
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.

+1
You seem correct to me.
+1
YES! 2/n-1 is correct. Nice question!
+1

your approach seems to be correct 2/n-1.