0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you can mark it as accepted answer. $\endgroup$ – GBat Sep 23 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.