What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?
-
06-11-2019 - |
Frage
Consider the recursive quick sort
with random pivoting
i.e. each time a random pivot element is chosen uniformly. When this randomized algorithm is being applied to an array with n
distinct element, what is the probability
that the smallest
and the greatest
element will be compared
during run of the algorithm.
Keine korrekte Lösung
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange