7.3-2

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

The no of times RANDOM is called depends on no of times RANDOMIZED-PARTITION is c alled.The Best case and worst case depends on partitioning(like earlier in normal quick sort case). The worst case occurs when partition of n gives n-1 and n-1 gives n-3. The recurrence for RANDOMIZED-PARTITION is: $$ T(n) = T(n-1)+ \theta(1) $$ $\theta(1)$ for the comparison if p < q.
By using substitution method the above recurrence is $\theta(n)$.
The best case occurs when when partition of n gives n/2 and n/2-1 elements:
$$ T(n) \leq 2 T(n/2)+\theta(1) $$ $$ T(n) \leq 2 T(n/2)+\theta(1) $$ Above recurrence is master theorem case 2. The recurrence is $\theta(n)$. for both best and wrost case the no of times RANDOMIZED-PARTITION is called is $\theta(n)$