Av. Case Complexity of Quicksort

Assume

• all keys distinct
• all permutations equally likely

Probability that split point is $i$, for $1\leq i \leq n$, is $1/n$

$$\begin{eqnarray*} &&A(n)=(n-1) +\frac 1 n (A(0)+A(n-1)+\\ && A(1)+A(n-2)+ \cd... ... &&\frac{A(n)}{n+1}-\frac{A(n-1)}{n}=\frac{2(n-1)}{n(n+1)} \\ \end{eqnarray*}$$

Let $B(n)=\frac{A(n)}{n+1}$ (Changing Variable)
Since $A(1)=0$, $B(1)=0$

$$\begin{eqnarray*} &&\Rightarrow B(n)-B(n-1)=\frac{2(n-1)}{n(n+1)}\\ &&B(n)=\f... ...1)}, B(1) = 0\\ &&B(n)=\sum_{i=2}^{n} \frac{2(i-1)}{i(i+1)}\\ \end{eqnarray*}$$

$f(n) = \frac{2(n-1)}{n(n+1)}$ continuous decreasing function

$$\begin{eqnarray*} &&B(n)\leq \int_{2}^{n} f(x)dx, f(1)=0\\ &&\frac{2(x-... ...(n+1)\log n\ [0.5cm] &&\Rightarrow A(n)\leq 1.4(n+1)\log_{2} n \end{eqnarray*}$$