# Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)

182 views

Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.

1 vote

proof

## Related questions

1
144 views
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
2
59 views
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
3
138 views
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
1 vote
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?