Notes - DAA HT23, Order statistics
Flashcards
What is the $i$-th order statistic for a set of $n$ elements?
The $i$-th smallest element.
What is 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)?
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 is within a certain window of the median.
Proofs (but really Programs)
Program a worst-case $\Theta(n^2)$ algorithm and average case $\Theta(n)$ algorithm for selecting the $i$-th smallest element of a list.
Todo.
Program a worst-case $\Theta(n)$ algorithm for selecting the median element of a list.
Todo.