edited by
8,202 views
13 votes
13 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)$
edited by

1 Answer

Best answer
33 votes
33 votes

 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
Answer:

Related questions

18 votes
18 votes
3 answers
1
makhdoom ghaya asked Nov 2, 2015
3,621 views
Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot...
9 votes
9 votes
2 answers
2
Arjun asked Dec 10, 2017
2,569 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$