# Average Case Running Time of Quicksort Algorithm

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)

• You are right, there's a typo in the website. However, this is not the complete analysis of average case complexity of quicksort, you'll have to find a different source for it. – Gokul Jul 18 at 13:37
• The website is completely wrong. There are other sources out there with a proper treatment of the problem, possibly not using any recurrence. – Yuval Filmus Jul 18 at 14:39

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*}