Assume array of size \(N\) with entries distinct and randomly ordered. Let \(C_N\) be the expected number of compares used by quicksort. Starting with the recurrence relation:

\[ \begin{aligned} C_N &= N + 1 + \sum_{k=1}^N \frac{1}{N}(C_{k-1} + C_{N-k}) & C_0 = 0\\ &= N + 1 + \frac{2}{N}\sum_{k=1}^N C_{k-1} &\text{by symmetry} \\ NC_N &= N(N + 1) + 2\sum_{k=1}^N C_{k-1} \\ (N-1)C_{N-1} &= (N - 1)N + 2\sum_{k=1}^{N-1} C_{k-1} &\text{for } N-1 \text{ instead of } N \\ NC_N - (N-1)C_{N-1} &= 2N + 2C_{N-1} &\text{subtract the last two equations}\\ NC_N &= (N+1)C_{N-1} + 2N & \text{note it's now linear time, not quadratic!}\\ \frac{C_N}{N+1} &= \frac{C_{N-1}}{N} + \frac{2}{N+1} &\text{divide both sides by } N(N+1) \\ \frac{C_N}{N+1} &= \frac{C_{N-1}}{N} + \frac{2}{N+1} = \frac{C_{N-2}}{N-1} + \frac{2}{N} + \frac{2}{N+1} &\text{telescope} \\ \frac{C_N}{N+1} &= \frac{C_1}{2} + \frac{2}{3} + \cdots + \frac{2}{N} + \frac{2}{N+1} & \text{note } C_1 = 2 \\ C_N &= (N + 1) (1 + \frac{2}{3} + \cdots + \frac{2}{N}) + 2 \\ C_N &\thicksim N (1 + \frac{2}{3} + \cdots + \frac{2}{N}) & f(x) \thicksim g(x) \text{ means} \lim_{x\rightarrow\infty}\frac{f(x)}{g(x)} = 1\\ C_N &\thicksim N + 2N(\frac{1}{3} + \cdots + \frac{1}{N}) \\ C_N &\thicksim N + 2N(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}) - 3N \\ C_N &\thicksim 2N \sum_{k=1}^N \frac{1}{k} - 2N \\ C_N &\thicksim 2N (\int_1^N\frac{1}{x}\,dx + \gamma) - 2N & \gamma = \text{Euler's constant} \approx .57721 \\ &= 2N \ln N - 2(1 - \gamma) N \qquad & \text{Isn't this amazing ?}\\ \end{aligned} \]

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 8:50 PM