Question: Consider the following problem. Given a set A of elements with a linear order and a positive integer k, k ≤ |A|, find the k-th smallest element of A. Obviously, one can solve this problem by sorting A and then taking the k-th smallest element. But one knows that the complexity of sorting by comparisons is in Θ(n · log n) and so this naive approach is too costly for searching for the k-th position in the sorted sequence only.