3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok. And why is $T(n)$ less or equal to the sum of these two values? $\endgroup$ – user175343 Dec 16 '14 at 22:53
  • $\begingroup$ Edited for clarification. Let me know if you have further questions. $\endgroup$ – afding Dec 16 '14 at 22:57
  • $\begingroup$ Do we use the average of the value $T(i-1)+T(n-i)$ because we want to find the expected time of Quicksort? $\endgroup$ – user175343 Dec 16 '14 at 23:07
  • $\begingroup$ Also when we select the pivot randomly is it then also constant time? $\endgroup$ – user175343 Dec 16 '14 at 23:08
  • $\begingroup$ Yep. In actuality, the worst-case for Quicksort is $O(n^{2})$, when you have a reverse-sorted list, cause you have to pick $n$ pivots and each inner-step will take $O(n)$ time as well. $\endgroup$ – afding Dec 16 '14 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy