The Gateway to Computer Science Excellence

0 votes

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.

0 votes

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.

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.

52,315 questions

60,432 answers

201,778 comments

95,257 users