TIFR CSE 2018 | Part B | Question: 7

Question

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 ?

• A. $\left(\dfrac{1}{n}\right)$
• B. $\left(\dfrac{2}{n}\right)$
• C. $\Theta \left(\dfrac{1}{n\log n}\right)$
• D. ${O} \left(\dfrac{1}{n^{2}}\right)$
• E. $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$

Comments

@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.

Answer 1

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

Comments

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

---

@mkagenius but comparisons happen only during ‘partitioning’ procedure. Quick-sort function anyway only calls itself on the newly formed partitions.

Just focus on ‘smallest’ and ‘largest’ keywords. And now try to select any random key for partitioning procedure and see whether you are able to guarantee that max-min elements will be compared.

And also, $\frac{1}{nlogn}$ would have sounded more valid according to your approach. But in worst case you could have $n^{2}$ comparisons. And yes that is why i selected D, which of-course in wrong.

Why is it wrong? Because those $n^{2}$ comparisons doesn’t necessarily have min-max comparisons, and therefore our sample-space itself is wrong.

---

superb explanation