The Gateway to Computer Science Excellence
+9 votes

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. $\left(\dfrac{1}{n}\right)$
  2. $\left(\dfrac{2}{n}\right)$
  3. $\Theta \left(\dfrac{1}{n\log n}\right)$
  4. ${O} \left(\dfrac{1}{n^{2}}\right)$
  5. $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$
in Algorithms by Veteran (424k points)
edited by | 498 views

@Arjun Sir please verify.

The largest and the smallest numbers will only be compared if either of them are chosen as the pivot in the very first split. In the subsequent splits they will never get compared since the first pivot divides the list into two and the largest and smallest number will be put in two different halves. The probability would thus be the probability to choose the largest or the smallest as the pivot in the very first step. Thus the required probability would be ${1 \over n}+ {1 \over n} =  {2 \over n}$.


$\frac{2}{n}$ since all elements are sorted only two cases i.e. when smallest element chooses as pivot or largest element choosen as pivot  the are compared only once , i.e. out of n elements only two number gives required one.

1 Answer

+12 votes
Best answer

 Probability that the smallest and the largest elements in the array are compared during a run of the randomized quicksort algorithm.

After the first split, first subpart of array will contain the minimum element and second subpart contains the maximum element. (Why?)

Choose any element say $x$, greater than or equal to smallest element. After partition, smallest element will be present in the left of it. The largest element will be present on the right sub array.

After the first split, there will be no more comparison between the largest and smallest element.

To have comparison between largest and smallest element we must choose anyone of the as the pivot element in the first split itself.

Among the $N$ elements we have to choose either the smallest element or the largest element. Selection will be uniform.

Probability $= 2 / n.$

by Boss (16.3k points)
selected by
E.g, 1,9,2,3,8,4,5, 6.  if series of pivots selected like 6, 4, 3, or 6, 4? Now consider the case where the list is very large.
If you select 6 as the pivot element. Then array split for your example 1, 9, 2, 3, 8 , 4, 5, 6 will be

Left subpart: 1 2 3 4 5 6

Right subpart: 8 9

Now solve these two subparts recursively.

Minimum and maximum element is 1 and 9. There will be no comparison between them.
Right.  thanks.
I am confused why is it not  $2 / nlogn$ Since total number of comparisons are $nlogn$ during the run of whole algorithm.

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
50,647 questions
56,492 answers
100,712 users