DAA HT23, Order statistics
Flashcards
@Define the $i$-th order statistic for a set of $n$ elements.
The $i$-th smallest element.
@Define the selection problem, given an array $A$ and some $i$.
Finding the $i$-th order statistic ($i$-th smallest element) in $A$.
What is the best possible time complexity of the selection problem (finding the $i$-th order statistic in an array)?
\[\Theta(n)\]
One worst-case $\Theta(n^2)$ and average-case $\Theta(n)$ algorithm for selecting the median element of a list works by selecting a random pivot to compare elements against. How does a more clever algorithm modify this to achieve a worst-case $\Theta(n)$ running time?
Selects a pivot it knows (by dividing the problem) is somewhere within a certain window of the median.