engineering recuitment UKPSC Polytechnic Lecturer Mock Test 2024 Algorithms Searching, Sorting and Hashing Sorting
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 largest elements in the array are compared during a run of the algorithm?
1
\(\dfrac{1}{n}\)
2
\(\dfrac{2}{n}\)
3
\(\theta\left(\dfrac{1}{n\:\log\:n}\right)\)
4
θ(1/n2)