38

RANDOMIZED-PARTITION(A.p.) 1 1 - RANDOMIP.D 2 exchange Alrl with Ali 3 return PARTITIONCA, P.) 2 RANDOMIZED-QUICKSORTA, P.) 1 ifpcr q=RANDOMIZED-PARTITION(A, P.) 3 RANDOMIZED-QUICKSORT(A, P. (-1) 4 RANDOMIZED-QUICKSORT(A q-11) What is the probability that the rightmost element becomes the pivot in a single call of RANDOMIZED-PARTITION? Select one: a 1 1 T-P+1 b c. 1 d. 1/2 1 e T-P