Question

Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?

a. 1/n

b. 1/(n-1)

c. 2/n

d. 2/(n-1)

Answer: d. 2/(n-1)

Answer 1

Total possibility of selecting pivot from array length n = n-1

No of Conditions where largest and smallest no is pivot = 2

( Until and unless maximum number and minimum number are pivots they can not be compared with each other)

Therefore,

Probability of not having comparison between smallest and largest number = 2/(n-1)