Randomized Select

Antagelse:

Purpose is to find the i’th smallest element in a list. Typically for finding $\frac{n}{2}$ aka the median

For example, using partition will place our element correctly. We therefore just need to check if the element we just sorted with partition is in the i’th location. If not, we discard all higher/lower values.

Runtime

Similar to Quicksort, but since we don’t sort we get a lower runtime

$$T(n)=T\left(\frac{n}{2}\right)+n$$ $$O(n)$$