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

Commit id: e260c16e401b8ad679faf6fe6cee6afed0f9c1da

deletions | additions      

       

\end{align*}  \end{subequations}  We calculate $(n-x)C(n-x)$ for some 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\]  We compute $nC(n)$ and So:  \begin{subequations}  \begin{align*}  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) &= \\  \end{align*}  \end{subequations}