The average complexity of quicksort is:
\[\begin{aligned} C(n) = \begin{cases} 1 & \text{if } n = 0\\ \frac{2}{n} \displaystyle\sum_{i=0}^{n-1} \left[ C(i) \right] + n & \text{if } n > 0 \end{cases}\end{aligned}\]
\(C(n-1), n > 0\) becomes:
\[\begin{aligned} C(n-1) = \frac{2}{n-1} \displaystyle\sum_{i=0}^{n-2} \left[ C(i) \right] + (n-1)\end{aligned}\]
We calculate \((n-x)C(n-x)\) for a few \(x \in \mathbb{N}\) and find out that: \[(n-x)C(n-x) = 2 \sum_{i=0}^{n-1-x} \left[C(i)\right] + n^2 + x^2 - 2nx\]
So:
\[\begin{aligned} nC(n) &= 2 \sum_{i=0}^{n-1} \left[C(i)\right] + n^2\\ (n-1)C(n-1) &= 2 \sum_{i=0}^{n-2} \left[C(i)\right] + n^2 + 1 - 2n\\ nC(n) - (n-1)C(n-1) &= 2 \left[ \sum_{i=0}^{n-1} \left[C(i)\right] - \sum_{i=0}^{n-2} \left[C(i)\right] \right] - 1 + 2n\\ &= 2C(n-1) + 2n - 1 \iff\\ nC(n) &= (2 + n - 1)C(n-1) + 2n - 1 \iff\\ C(n) &= (1 + \frac{1}{n})C(n-1) + 2 - \frac{1}{n}\end{aligned}\]
This gives us that: \[C(n+1) = (1 + \frac{1}{n+1})C(n) + 2 - \frac{1}{n+1}\\ \Updownarrow\\ C(n+1) - (1 + \frac{1}{n+1})C(n) = 2 - \frac{1}{n+1}\\ \Updownarrow\\ \frac{C(n+1)}{\prod_{k=0}^{n}\left[1+\frac{1}{k+1}\right]} - \frac{(1 + \frac{1}{n+1})C(n)}{\prod_{k=0}^{n}\left[1+\frac{1}{k+1}\right]} = \frac{2 - \frac{1}{n+1}}{\prod_{k=0}^{n}\left[1+\frac{1}{k+1}\right]}\\ \Updownarrow\\ \frac{C(n+1)}{\prod_{k=0}^{n}\left[1+\frac{1}{k+1}\right]} - \frac{C(n)}{\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]} = \frac{2 - \frac{1}{n+1}}{\prod_{k=0}^{n}\left[1+\frac{1}{k+1}\right]}\\ \Updownarrow\\ \frac{C(n+1)}{n+2} - \frac{C(n)}{n+1} = \frac{2 - \frac{1}{n+1}}{n+2}\\ \Updownarrow\\ \sum_{m=0}^{n-1}\left[\frac{C(m+1)}{m+2} - \frac{C(m)}{m+1}\right] = \sum_{m=0}^{n-1}\left[\frac{2 - \frac{1}{m+1}}{m+2}\right]\\ \Updownarrow\\ \frac{C(n)}{n+1} - \frac{C(0)}{1} = \sum_{m=0}^{n-1}\left[\frac{2 - \frac{1}{m+1}}{m+2}\right]\\ \Updownarrow\\ C(n) = \left(n+1\right)\left(C(0) + \sum_{m=0}^{n-1}\left[\frac{2 - \frac{1}{m+1}}{m+2}\right]\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + \sum_{m=0}^{n-1}\left[\frac{3}{m+2} - \frac{1}{m+1}\right]\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + 3\sum_{m=0}^{n-1}\left[\frac{1}{m+2}\right] - \sum_{m=0}^{n-1}\left[\frac{1}{m+1}\right]\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + 3\sum_{m=2}^{n+1}\left[\frac{1}{m}\right] - \sum_{m=1}^{n}\left[\frac{1}{m}\right]\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + 2\sum_{m=2}^{n+1}\left[\frac{1}{m}\right] + \frac{1}{n+1} - 1\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + 2\left(\sum_{m=1}^{n}\left[\frac{1}{m}\right] - 1 + \frac{1}{n+1}\right) + \frac{1}{n+1} - 1\right)\\ \Updownarrow\\ C(n) = (n+1)\left(C(0) + 2H_n - 3 + \frac{3}{n+1}\right)\\ \Updownarrow\\ C(n) = 2nH_n + 2H_n - 2n + 1\] Since \(H_n \in \mathcal{O}(\log{n})\), we get that \(C(n) \in \mathcal{O}(n\log{n})\).