Niclas Alexandersson edited d) Quicksort average complexity.tex  about 10 years ago

Commit id: 9bc463d825d755369873dd688f1f8074322c6b3d

deletions | additions      

       

\[  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} \frac{1}{n+1}\\  \Updownarrow\\  \frac{C(n+1)}{\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]} - \frac{(1 + \frac{1}{n+1})C(n)}{\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]} = \frac{2 - \frac{1}{n+1}}{\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]}\\  \]