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.

in Algorithms by | 272 views

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 ??


@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. 

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

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,501 answers
95,325 users