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
edited by | 765 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

+16 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.$

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.

@mkagenius your choice of sample space does not correspond to your selection of favorable cases.

The sample space should be the whole set of elements. It is not the number of comparisons. The question is essentially asking - which elements can be selected as pivot so that a min-max comparison is ensured during a run of the partition procedure. There are only 2 - the min and the max of the array.

Hmm, it never mentioned that it is asking about partition procedure, it started with "quicksort algorithm" and ended with "run of the algorithm". How does one conclude it is only referring to partition procedure?

Moreover, I am surprised that people are not confused at all, atleast be a little bit confused, come on. If I were the setter of the problem, and I would have marked $2/nlogn$ as the answer even then people have had explanation for that as well. Its kind of confirmation bias going on with people.
>what is the probability that the smallest and the largest elements in the array are compared during a run of the algorithm?

When are elements compared? When a pivot is chosen.

When is a pivot chosen? During a run of the partition procedure.

What are we looking for? A pivot which would force the comparison of min and max elements.

What sort of pivot would do that? Only that pivot which is the min or the max of the array itself.

How many favorable cases? Two - when the pivot is the min, and when the pivot is the max.

This should clear it up. There is no ambiguity and definitely no confirmation bias.
Now suppose the question was: What is the probability of $any$ two numbers being compared? Since there are total $n log n$ comparisons, $numerator$ will become $n log n$ and the $denominator$ according to the accepted answer will be $n$, so the probaility will be $log n$ which will be more than $1$.

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,315 questions
60,428 answers
95,238 users