Mazdak Farrokhzad edited d) Quicksort average complexity.tex  about 10 years ago

Commit id: 5b6554e75dd56f342330227f5dc3e2329a23e7ec

deletions | additions      

       

\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)\\  \]