9.6.3 Quicksort: Average Case Analysis

Assume that all initial orderings of the keys are equally likely;

• Assume that the keys are distinct

 

 

Note that the presence of equal keys will make the sorting easier, not harder.

• Also assume that when we call quicksort (i, j), all orders for A[i]SUP> ... A[j] are equally likely.

 

 

Let T(n) = average time taken by quicksort to sort n elements

• T(1) = C₁ where C₁ is some constant.
• Recall that the pivot is the larger of the first two elements.
• When n > 1, quicksort splits the subarray, taking C₂ntime, where C₂ is another constant.

Also, since the pivot is the larger of the first two elements, left groups tend to be larger than the right groups.

The left group can have i elements where i = 1, 2,..., n - 1, since the left group has at least one element and the right group also has at least one element.

Let us fix i and try to compute the probability:

                                                P{ left group has i elements}

Now, left group has i elements

$\Rightarrow$pivot must be the (i + 1)^stelement among the n elements
 

If the pivot is in position 1, then the element in position 2 is one of the i smaller elements and vice-versa.

P{ Position 1 contains one of the i smaller elements }

                                                                    = $$\left(\vphantom{\frac{i}{n-1}}\right.$$$${\frac{i}{n-1}}$$$$\left.\vphantom{\frac{i}{n-1}}\right)$$$$\left(\vphantom{\frac{1}{n}}\right.$$$${\frac{1}{n}}$$$$\left.\vphantom{\frac{1}{n}}\right)$$
Similarly,

P{ Position 2 contains one of the i smaller elements}

                                                                     = $$\left(\vphantom{\frac{1}{n}}\right.$$$${\frac{1}{n}}$$$$\left.\vphantom{\frac{1}{n}}\right)$$$$\left(\vphantom{\frac{i}{n-1}}\right.$$$${\frac{i}{n-1}}$$$$\left.\vphantom{\frac{i}{n-1}}\right)$$
Therefore,

P{ left group has i elements} 

                                                                    = $${\frac{2i}{n(n-1)}}$$
This leads to

                                    T(n) $$\leq$$C₂n + $$\sum_{i=1}^{n-1}$$$${\frac{2i}{n(n-1)}}$$$$\left\{\vphantom{ T(i) + T(n-i) }\right.$$T(i) + T(n - i)$$\left.\vphantom{ T(i) + T(n-i) }\right\}$$
Using
$$\sum_{i=1}^{n-1}$$f (i) = $$\sum_{i=1}^{n-1}$$f (n - i),
we get
                                            T(n) $$\leq$$C₂n + $${\frac{1}{n-1}}$$$$\sum_{i=1}^{n-1}$$$$\left\{\vphantom{ T(i) + T(n-i) }\right.$$T(i) + T(n - i)$$\left.\vphantom{ T(i) + T(n-i) }\right\}$$
The above expression is in the form it would have been if we had picked a truly random pivot at each step.

The above simplifies to:
                                            T(n) $$\leq$$C₂n + $${\frac{2}{n-1}}$$$$\sum_{i=1}^{n-1}$$T(i)
The above is the recurrence that one would get if all sizes between 1 and n - 1for the left group were equally likely. Thus picking the larger of the two elements doesn't really affect the size distribution.

We shall guess the solution
                                           T(n) $$\leq$$Cnlog n
for some constant C and prove its correctness using induction.

Basis:

                                    n = 2 $$\Rightarrow$$Cnlog n = 2C
 

which is correct.

Induction Step:

AssumeT(i) $\leq$Cilogi$\forall$i < n.

$$\leq {\frac{2C}{n-1}} \sum_{i=1}^{n-1}$$ T(n)

$$\leq {\frac{2C}{n-1}} \sum_{i=1}^{n/2} {\frac{2C}{n-1}} \sum_{i=\frac{n}{2} + 1}^{n-1}$$

$$\leq {\frac{2C}{n-1}} \sum_{i=1}^{n/2} {\frac{n}{2}} {\frac{2C}{n-1}} \sum_{i=\frac{n}{2} + 1}^{n-1}$$

$$\leq {\frac{Cn}{4}} {\frac{Cn}{2(n-1)}}$$

PickingC$\geq$ 4C₂, we have,

                                C₂n - $${\frac{Cn}{4}}$$$$\geq$$ 0
Thus T(n) is O(nlog n)