Expected time of Quicksort

Question

I am reading the proof of the theorem:

The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time.

The proof is this:

For simplicity in the timing analysis assume that all elements of $S$ are distinct.

This assumption will maximize the sizes of $S_1$ and $S_3$, and therefore maximize the average time spent in the recursive calls (QUICKSORT($S_1$), QUICKSORT($S_3$)).

Let $T(n)$ be the expected time required by QUICKSORT to sort a sequence of $n$ elements.

Clearly, $T(0)=T(1)=b$ for some constant $b$.

Suppose that element $a$ (the pivot, that is selectes randomly) is the ith smallest element of the $n$ elements in sequences.

Then the two recursive calls of QUICKSORT (QUICKSORT($S_1$), QUICKSORT($S_3$)) have an expected time of $T(i-1)$ and $T(n-i)$, respectively.

Since $i$ is equally likely to take on any value between $1$ and $n$, and the balance of QUICKSORT($S$ clearly rewquires time $cn$ for some constant $c$, we have the relationship: $$T(n) \leq cn +\frac{1}{n} \sum_{i=1}^{n} [T(i-1)+T(n-i)], \text{ for } n\geq 2 \tag {1}$$

Algebraic manpulation of $(1)$ yields $$T(n) \leq cn +\frac{2}{n}\sum_{i=0}^{n-1}T(i) \tag {2}$$

We shall show that for $n \geq 2$, $T(n) \leq kn \log_e n$, where $k=2c+2b$ and $b=T(0)=T(1)$.

For the basis $n=2$, $T(2)\leq 2c+2b$ follows immediately from $(2)$.

For the induction step, write $(2)$ as $$T(n) \leq cn +\frac{4b}{n}+\frac{2}{n}\sum_{i=2}^{n-1} k i \log_e i \tag {3}$$

Since $i \log_e i$ is concave upwards, it is easy to show that $$\sum_{i=2}^{n-1} i \log_e i \leq \int_2^n x \log_e x dx \leq \frac{n^2 \log_e n}{2}-\frac{n^2}{4} \tag {4}$$

Substituting $(4)$ in $(3)$ yields $$T(n) \leq cn+\frac{4b}{n}+kn \log_e n-\frac{kn}{2} \tag {5}$$

Since $n\geq 2$ and $k=2c+2b$, it follows that $cn+4b/n\leq kn/2$.

Thus $T(n)\leq kn \log_e n$ follows $(5)$.

$$$$

How did we get the relation $(1)$ ?

Thanks in advance.

Edit:

Can you explain to me this sentence:

"This assumption will maximize the sizes of $S_1$ and $S_3$, and therefore maximize the average time spent in the recursive calls (QUICKSORT($S_1$), QUICKSORT($S_3$)). "

?

Why does this maximize the average time spent in the recursive calls?

Answer 1

Quicksort boils down to:

1. Selecting a pivot

2. Separate big list into a "smaller than pivot" list $S_{1}$ and "larger than pivot" list $S_{2}$

3. Sort $S_{1}$ and $S_{2}$ separately, call result $S_{1}'$ and $S_{2}'$.

4. Combine $S_{1}'$ and $S_{2}'$ and pivot into final, sorted list $S'$.

   Selecting a pivot randomly is constant time. Hence, it follows that

$T(n) \leq [\text{Step 2}] + [\text{Step 3}] + [\text{Step 4}]$

Step 2 takes $an$ time for some constant $a$. You just make a pass through the list, compare it to the pivot, and throw it in either $S_{1}$ or $S_{2}$. Step 4 takes at most $bn$ time, for less obvious reasons. Hence Steps 2 and 4 take up at most $cn$ time for a constant $c$.

Step 3 remains. The expression

$\displaystyle\frac{1}{n}\displaystyle\sum_{i = 1}^{n}\left[T(i-1)+T(n-i)\right]$

is the average of the value $T(i-1)+T(n-i)$ over all $i$, and that's the recursive step, sorting two strictly smaller lists. Hence the above sum is the average time needed to do Step 3.

In conclusion, the whole process takes less than $cn + \displaystyle\frac{1}{n}\displaystyle\sum_{i = 1}^{n}\left[T(i-1)+T(n-i)\right]$ time.