A random number generator can be expensive Assuming the rand

A random number generator can be expensive. Assuming the randomized version of quicksort splits every level perfectly in half, how many times is random() called for input size n?

Solution

random() is called once for each time randomized-version is called, so we can just consider the calls to randomized-version by RandomQuickSort.

The worst case occurs when the partitioning produces one subproblem of size n-1 and one of size 0 each time it is called. The recurrence for the calls to randomized-version is then

T(n) = T(n 1) + T(0) + (1) T(0) = 0

because randomized-version is not called on a subproblem of size 0, so T(n) = T(n 1) + (1)

Therefore, in the worst case, T(n) = (n).

The best case occurs when the partitioning produces two subproblems of size at most n/2. It is this because one will have [n/2] elements and one will have [n/2] 1. The recurrence for the calls to randomized-version is then

T(n) 2T(n/2) + (1)

By case 1 of the Master Theorem,

T(n) has the solution T(n) = (n) in the best case.

So, (n) calls are to be made to random for input size n in the best and worst cases.