Randomized QuickSort and Randomized Select Analysis

Randomized QuickSort

Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.

Randomized Select

Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.