Chapter 7.4, Problem 42E

To determine

(a)

To prove:

The average number of comparisons used by the quick sort algorithm isE(X)(where the sample space is the set of alln ! permutations ofnintegers).

To determine

(b)

To prove:

$X={\displaystyle {\sum }_{k=2}^n{\displaystyle \sum _{j=1}^{k-1}{I}_{j,k}}}$.

To determine

(c)

To prove:

$E\left(X\right)={\displaystyle {\sum }_{k=2}^n{\displaystyle {\sum }_{j=1}^{k-1}p}}$

To determine

(d)

To prove:

>p>p(thejthsmallest element and thekthsmallest element are compared),wherek >j, equals 2 /(k-j+ 1)..

To determine

(e)

To prove:

Use parts (c) and (d) to show that $E\left(X\right)=2\left(n+1\right)\left({\displaystyle {\sum }_{i=2}^n\frac{1}{i}}\right)-2\left(n-1\right)$

To determine

(f)

Conclude from part (e) and the fact that ${\displaystyle {\sum }_{j=1}^{n}1/j}\ln n+\gamma$, where $\gamma =0.57721\dots$ is Euler’sconstant, that the average number of comparisons used by the quick sort algorithm is $\Theta \left(n\log n\right)$.