Chapter 9, Problem 4P

(a)

Program Plan Intro

T give an exact expression for $E[Xijk]$ .

(b)

Program Plan Intro

To show that. $E[Xk]\le 2\left({\displaystyle \sum _{i=1}^k}{\displaystyle \sum _{j=k}^n\frac{1}{j-i+1}+}{\displaystyle \sum _{j=k+1}^n\frac{j-k-1}{j-k+1}+}{\displaystyle \sum _{i=1}^{k-2}\frac{k-i-1}{k-i+1}}\right)$ .

(c)

Program Plan Intro

To show that $E[Xk]\le 4n$ .

(d)

Program Plan Intro

To conclude that RANDOMIZED-SELECT runs in expected time $O(n)$ .