Register

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?

• retagged by
455 views
0 votes
0 votes
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)
• retagged by
User Avatar

1 Answer

0 votes
0 votes
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)
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
1,167 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
User Avatar
1 votes
1 votes
0 answers
3
Sahil Gupta asked Nov 25, 2014
775 views
Let X be the random variable on the set of permutations of a set of n distinct integers {a 1 , a 2 , . . . , a n } with a1 < a2 < · · · < an such that X(P) equals the number of comparisons used by the bubble sort to put these integers into increasing order.
Answer the following part:a) Show that, under the assumption that the input is equally likely to be any of the n! permutations of theseintegers, the average number of com...
User Avatar
Link Copied!