Average Case Running Time of Quicksort Algorithm

Question

From this website, it states that the average case of Quicksort algorithm is

  T(n) = T(n/9) + T(9n/10) + θ(n)

Im a bit confused. Is it supposed to be ?

  T(n) = T(n/10) + T(9n/10) + θ(n)

Answer 1

The average case running time of quicksort satisfies the recurrence $$ T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n), $$ with base case $T(0) = \Theta(1)$.

In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order of summation, we get $$ T(n) = \frac{2}{n} \sum_{i=0}^{n-1} T(i) + n + 1, $$ and so $$ nT(n) = 2\sum_{i=0}^{n-1} T(i) + n(n+1). $$ This implies that $$ (n+1)T(n+1) - nT(n) = 2T(n) + 2(n+1), $$ and so $$ T(n+1) = \frac{n+2}{n+1} T(n) + 2. $$ Unrolling this gives $$ \begin{align*} T(n) &= 2 + \frac{n+1}{n} T(n-1) = 2 + \frac{n+1}{n} 2 + \frac{n+1}{n-1} T(n-2) = \cdots \\ &= 2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2}\right] + \frac{n+1}{1} T(0) \\ &= 2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2} + \frac{n+1}{1} \right] \\ &= 2(n+1) \left[\frac{1}{n+1} + \cdots + \frac{1}{1} \right] \\ &= 2(n+1) H_{n+1} \\ &= \Theta(n\log n). \end{align*} $$

---

A different way of analyzing the running time of quicksort in the average case computes the average number of comparisons. Due to linearity of expectation, it suffices to calculate the probability that two elements are compared. You can see both methods worked out in Section 3.4 of lecture notes from CMU.