The Gateway to Computer Science Excellence

+1 vote

Que – 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 $2^{nd}$ largest elements in the array are compared during a run of the algorithm?

I am getting – $\frac{2}{n}+(\frac{1}{n}*\frac{2}{n-1}) = \frac{2}{n-1} $

Please verify.

0

I think it will be.

among the N elements, we have to choose either the smallest element or 2nd largest element.

So, $\frac{1}{n} + \frac{1}{n}*\frac{1}{n-1} = \frac{1}{n-1}$ .

Am I right ??

0

@kumar.dilip Acc. to me, those 2 elements are compared only when-

Case 1 - Any of them is chosen as a pivot during $1^{st}$ split.

Case 2- Largest element is chosen as a pivot during $1^{st}$ split and smallest or $2^{nd}$ largest element is chosen as a pivot during $2^{nd}$ split.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,429 answers

195,205 comments

99,907 users