7-5

7-5 Median-of-3 partition
One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.4-6.) For this problem, let us assume that the elements in the input array A[1..n] are distinct and that $n \geq 3$. We denote the
sorted output array by A[1..n] . Using the median-of-3 method to choose the pivot element x, define pi = Pr{x=A'[i]}
a. Give an exact formula for $p_i$ as a function of n and i for i = 2,3,...,n-1. (Note that $p_1 = p_n = 0$.)
b. By what amount have we increased the likelihood of choosing the pivot as x = $A'\big[\lfloor(n+1/2\rfloor\big]$ , the median of A[1..n] , compared with the ordinary implementation? Assume that $n \rightarrow \infty$, and give the limiting ratio of these probabilities.
c. If we define a “good” split to mean choosing the pivot as x = A[i] , where $n/3 \leq i \leq 2n/3$, by what amount have we increased the likelihood of getting a good split compared with the ordinary implementation? (Hint: Approximate the sum by an integral.)
d. Argue that in the $\Omega(n lg n)$ running time of quicksort, the median-of-3 method affects only the constant factor.
a. The probability of choosing a pivot element x, pi = Pr{x=A'[i]} depends picking three elements and one of two elements should be less than pivot element and one element should be greater than pivot. pi = Pr{ probability of choosing three elements from set n and one of two elements should be less than pivot and one of the element should be greater than pivot} since these are independent events pi = Pr{ probability of choosing three elements from set n} Pr{one of two elements should be less than pivot} Pr{one of the element should be greater than pivot} $$p_i = \frac{3}{n} \frac{2 . (i-1)}{n-1} \frac{n-i}{n-2} $$ $$p_i = \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ b. The probability will remain same for in both cases while chossing $A'\big[\lfloor(n+1/2\rfloor\big]$ because all elements have equal chance. subsitute $\frac{(n+1)}{2}$ for i ignoring floor conditions $$p_i= \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{6 . (\frac{(n+1)}{2}-1)(n-\frac{(n+1)}{2}}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{6 . (\frac{(n-1)}{2})(\frac{(n-1)}{2}}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{3 . (n-1)}{2 n . (n-2)}$$ Lets take ratio of improved method with original method. The original has a probability of 1/n taking ratio of probability and $n \rightarrow \infty$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{ \frac{3 . (n-1)}{2 n . (n-2)}}{\frac{1}{n}}$$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{3 . (n-1)}{2 . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{3 . (1-\frac{1}{n})}{2 . (1-\frac{2}{n})}$$ $$p_{\frac{(n+1)}{2}}= \frac{3}{2}$$ we have increased the chance of selecting by 50 %(3/2-1).
c. The probability of selecting a value between $n/3$ and $2n/3$ for original method is $(2n/3-n/3)/n $ = $1/3$ The probability of selecting an element between $n/3$ and $2n/3$ for median of 3 method is $$p_i = \sum_{i = \frac{n}{3}}^{\frac{2n}{3}} \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ using approximation by integrals $$p_i = \int_{\frac{n}{3}}^{\frac{2n}{3}} \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \int_{\frac{n}{3}}^{\frac{2n}{3}} (i-1)(n-i) $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \int_{\frac{n}{3}}^{\frac{2n}{3}} -i^2+(n+1)i-n $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \Big[-\frac{i^3}{3}+(n+1)\frac{i^2}{2}-n i \Big]_{\frac{n}{3}}^{\frac{2n}{3}} $$ substituting the limits in the above equation and solving gives $$\frac{13 n ^2 -27n}{27n^2-81n+54}$$ when $n \rightarrow \infty$ $$\lim_{n \rightarrow \infty}\frac{13 -27/n}{27-81/n+54/n^2}$$ $$\frac{13}{27}$$ If we take teh ratio of improved method with the orginal method we get $$\frac{13}{27} \frac{1}{3}$$ $$\frac{13}{9}$$ = 1.44 Thus we increased the chance of choosing median by 44 %.
d.The best case occurs for the original method when we partition in to two subarrays of sizes n/2 and n/2. $$T(n) = 2T(n/2)+\theta(n)$$ Even if we use the median of 3 method(will add little extra time in finding the median) running time will be $\Omega(n log n)$ because we are only improving the probability of finding the median but not the running time.