Explaining Proof of Quick-Sort's O(nlog n) Expected Running Time

[evinda]

Hello! (Wave)

View attachment 4422

View attachment 4423I am trying to understand the proof that the expected running time of quick-sort is $O(n \log n)$.

Could you maybe explain it to me?

 

[evinda]

Suppose that we use the following algorithm:

Quicksort(S):
1.  if S contains at most one element then return S
    else
2.       choose an element a randomly from S;
3.       let S1, S2, and S3 be the sequences of elements in S less than, equal to, and greater than a, respectively;
4.       return Quicksort(S1) followed by S2 followed by Quicksort(S3)

I have tried the following:

Let $$T(n)$$ be the expected time required by the Quicksort algorithm in order to sort a sequence of $$n$$ elements. We have that $$T(0)=T(1)=b$$ for a constant $$b$$.

We suppose that the elements $$a$$ is the $$i$$-th smallest elements of the $$n$$ elements of the sequence $$S$$.
Then the 2 recursive calls of Quicksort have expected time $$T(i-1)$$ and $$T(n-i)$$, respectively.
Since the lines 2-3 require time $$O(n)$$ and the line 1 requires time $$O(1)$$, we have the following recurrence relation:

$$T(n) \leq cn+ \frac{1}{n} \sum_{i=1}^n \left[ T(i-1)+T(n-i)\right], n \geq 2$$

$$\\ T(n) \leq cn+ \frac{1}{n} \sum_{i=1}^n \left[ T(i-1)+T(n-i)\right] \\ \leq cn+ \frac{1}{n} \sum_{i=1}^n \left[ 2T(i-1) \right] =cn+ \frac{2}{n} \sum_{i=0}^{n-1} T(i) \\ \Rightarrow T(n) \leq cn+ \frac{2}{n} \sum_{i=0}^{n-1} T(i)(1)$$

We will show that for $$n \geq 2$$, $$T(n) \leq k n \log n$$, for $$k=2(c+b)$$ positive.

For $$n=2$$: From the relation (1) we have $$T(2) \leq c2+ 2b=2(c+b) \checkmark$$

We suppose that $$T(n) \leq k n \log n$$ γfor some $$n \geq 2$$.

We will show that $$T(n+1) \leq k (n+1) \log (n+1)$$ .

From the relation (1) we have $$T(n+1) \leq c(n+1)+ \frac{2}{n+1} \sum_{i=0}^{n} T(i) \leq c(n+1)+ \frac{2}{n+1} (n+1) T(n)= c(n+1)+2T(n) \leq c(n+1)+2 k n \log n \leq (n+1) (c+2k \log n)$$How could we continue? Or should we use strong induction?