Cormen Edition 3 Exercise 7.3 Question 2 (Page No. 180)

Question

RANDOMIZED-QUICKSORT(A, p, r)
1     if p < r
2     q = RANDOMIZED-PARTITION(A, p, r)
3     RANDOMIZED-QUICKSORT(A, p, q – 1)
4     RANDOMIZED-QUICKSORT(A, q + 1, r)


RANDOMIZED-PARTITION(A, p, r)
1     i = RANDOM(p, r)
2     exchange A[r] with A[i]
3     return PARTITION(A, p, r)

 

When RANDOMIZED-QUICKSORT runs, how many calls are made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of  $\Theta$ notation.

Answer 1

In the worst case, RANDOM returns the index of the largest element each
time it’s called, so $\Theta (n)$ calls are made. In the best case, RANDOM returns
the index of the element in the middle of the array and the array has distinct
elements, so $\Theta (lg n)$ calls are made.