$(3$ points$)$ A randomized quick sort works as follows. For ease of discussion we assume that the sequence we want to sort, $K$~$=(k_1,$dots,$k_n),$ is a permutation of $1$ to $n.$ We randomly and uniformly pick a key $k$ from $K.$ Then we partition $K$ into two subsets $-K_1$ that has keys less than $k$ and $K_2$ that has keys greater than $k.$ Then we recursively sort $K_1$ and $K_2,$ and combine the results with $k$ to get the sorted sequence.

The number of key comparisons will always be maximized when the keys in $K$ are already sorted.

Let $|K_1|$ and $|K_2|$ be the number of keys in $K_1$ and $K_2$ respectively. The expected value of max$(|K_1|,|K_2|)$ is $\frac{2}{3}n.$

The algorithm will compare two keys $k_i$ and $k_j$ at most once, so the number of key comparisons is $O(n^2).$

The probability that the algorithm will compare $k_i$ and $)i>j(1$ is $\frac{2}{i-j+1}.$

Let $P=\{(i,j)|1i,jn,ij\}.$ The expected total number of key comparisons is $({\displaystyle \underset{(i)}{\overset{?}{}}},$jinP$\frac{1}{|k_1-k_j|+1}.$