1,022 views
2 votes
2 votes

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.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
3 answers
1
ajaysoni1924 asked Sep 2, 2019
3,469 views
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexit...
0 votes
0 votes
1 answer
4
Purvi Agrawal asked Oct 13, 2018
3,716 views
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as thepivot. Calculate the worst case time complexity of the algorithm.