(a)

Formula for as a function of n is

(b)

Assume that n is even, since it doesn’t affect the ratio in the limit.

When, then we get

If i is odd, then

and the ratio is

Otherwise,

And the ratio is

Assume that n approaches infinity, the limiting ration is .

(c)

For the new method, the probability of a good split is

To approximate by an integral, we will use the variable t to mean the fraction of the way from 1 to n, then are all nearly 1 (all of the way through).

So, the approximately integral is,

Therefore, the increase in likelihood of getting good split compare to the ordinary implementation is .

(d)

The best possible running time for any version of quick sort would be achieved when the median is picked for the pivot every time. But the process of picking median takes , because the array is divided into half every time and the recursion handles both halves. So, in the scheme for picking the pivot using median-of-3 also takes . Hence the median-of-3 method has no effect on the net asymptotic running time.

Therefore, the median-of-3 method affects ruing time of quick sort only by the constant factor.

a.

A randomized algorithm for fuzzy-sorting n intervals will be same as the randomized quicksort in modified form. The lower bound of the n closed interval is which is the left end in the quicksort, so it will be better to sort and the comparison operators are replaced. The changes in PARTITION is required. Let the element be y located at the position i, so use y.a and y.b to denote and respectively.

The algorithm is as follows:

MODIFIED-PARTITION (A, p, r)

1. Pick the left end-points of all intervals that is

2. Pick the median O(n) time.

3. Pick the corresponding interval as pivot and partition intervals according to .

4. Divide the original problem into two sub-problems each of size

5. The intervals in left sub-problem have left endpoints smaller than pivot, so list all of them before pivot in output.

6. The intervals in right sub-problem have left endpoints larger than pivot, so list all of them after pivot in output.

7. Call FUZZY-SORT recursively on left sub-problem and right sub-problem.

8. Combine result with pivot in O(n) time.

b.

Since the algorithm runs as the quicksort so the expected runtime is . If the intervals overlap then there exists a value, then the condition that satisfies the condition is or for each iteration of for loop. Call the FUZZY-PARTITION once and the run time is