7.4-4

Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n lg n)$. The expected running time of Randomized-QUICKSORT is $$E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 2/j-i+1 $$ $$E[X] = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} 2/k $$ $$E[X] = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} 2/k $$ using approximation by integration (Appendix A)(sum can be bounded by integrals)(monotonically decreasing series) $$E[X] \geq \sum_{i=1}^{n-1} 2 \int_{k=2}^{n-i+2} 1/k $$ $$E[X] = \sum_{i=1}^{n-1} 2 ( ln(n-i+2)-ln2) $$ $$E[X] = \sum_{i=1}^{n-1} 2 (ln(n-i+2)-ln2) $$ $$E[X] = 2(ln(n+1)+ln n + ln(n-1) +..+ ln 3 )- ln2(n(n-1)) $$ $$E[X] \geq 2 (ln(n)+ ln n + ln(n-2)+...+ln 2 + ln 1) - ln2 (n(n-1))$$ $$E[X] \geq 2 (ln n!) - ln2 (n(n-1))$$ $$E[X] = \Omega(n log n)$$