K-selection in hypercubes

This paper deals with the problem of finding the K smallest elements out of a totally ordered but non sorted set of N elements. This problem, called K-selection, arises often in statistics, image processing and distributed computing. The author´s algorithm has a worst-case complexity O(log K(log log K)²+log K log log ^N/_K+log ^N/_K) on a hypercube of size N, which is asymptotically optimal when K=(log N)^β, for any constant β. This is a great improvement on previous results. The author addresses the universal K-selection problem as well