Expected Run Time

We get a mix of good and according to their relative probabilities.

\begin{eqnarraystar}
T(n) &=& n + {1/n}\; \sum_{k = 0}^{n-1} [T(k) + T(n-k-1)]\\...
 .../4) T(n-1)\\ &\le& n + 1/2\; [T(3n/4) + T(n/4)] + 1/2\; T(n-1)\end{eqnarraystar}


next up previous
Next: Asymptotic Bound Up: RANDOMIZED QUICKSORT Previous: Good and Bad Splits