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

Commit id: a3ce486174f0d8827045c8ee1fdbc69934b06b04

deletions | additions      

       

\Updownarrow\\  C(n) = \left(\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]\right)\left(\frac{C(0)}{\prod_{k=0}^{-1}\left[1+\frac{1}{k+1}\right]} + \sum_{m=0}^{n-1}\left[\frac{2 - \frac{1}{m+1}}{\prod_{k=0}^{m}\left[1+\frac{1}{k+1}\right]}\right]\right)\\  \Updownarrow\\  C(n) = \left(n+1\right)\left(C(0) + \sum_{m=0}^{n-1}\left[\frac{2 - \frac{1}{m+1}}{n+2}\right]\right)\\  \Updownarrow\\  C(n) = \left(n+1\right)\left(1 + \frac{1}{n+2}\left(\sum_{m=0}^{n-1}\left[2\right]-\sum_{m=0}^{n-1}\left[\frac{1}{m+1}\right]\right)\right)\\  \Updownarrow\\  C(n) = \left(n+1\right)\left(1 + \frac{1}{n+2}\left(2n-H_n\right)\right) \frac{1}{m+1}}{m+2}\right]\right)\\  \]