Selecting the k largest elements with parity tests

0.00 Avg rating—0 Votes

Article ID:	iaor20013470
Country:	Netherlands
Volume:	101
Issue:	1/3
Start Page Number:	187
End Page Number:	196
Publication Date:	Apr 2000
Journal:	Discrete Applied Mathematics
Authors:	Lam Tak Wah, Ting Hing Fung

Abstract:

In this paper we study the problem of finding k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that n+(k−1)logn+O(1) queries are necessary for any deterministic algorithm using parity tests only. We also present a randomized algorithm with error probability O(l/n^c) using only O(log²n+klogn) parity tests, where c>1 is any fixed constant.

Reviews

Required fields are marked *. Your email address will not be published.