this is for holding javascript data
Niclas Alexandersson edited d) Quicksort average complexity.tex
about 10 years ago
Commit id: 0cdc53c6ed0520bfff1fd14f0ce3406fa5357d85
deletions | additions
diff --git a/d) Quicksort average complexity.tex b/d) Quicksort average complexity.tex
index 43b3470..23bbb83 100644
--- a/d) Quicksort average complexity.tex
+++ b/d) Quicksort average complexity.tex
...
\Updownarrow\\
\sum_{m=0}^{n-1}\left[\frac{C(m+1)}{\prod_{k=0}^{m}\left[1+\frac{1}{k+1}\right]} - \frac{C(m)}{\prod_{k=0}^{m-1}\left[1+\frac{1}{k+1}\right]}\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]\\
\Updownarrow\\
\frac{C(n)}{\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]} - \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] \frac{1}{m+1}}{\prod_{k=0}^{m}\left[1+\frac{1}{k+1}\right]}\right]\\
\Updownarrow\\
C(n) = \left(\prod_{k=0}^{n-1}\left[1+\frac{1}{k+1}\right]\right)\left(C(0) + \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)
\]