https://tracker.cse.buffalo.edu/Ticket/Display.html?id=16035

Comments: castor
ContactPerson: boxer@cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2002-17
%U /home/csestaff/stock/head.ps
%A Boxer, Laurence
%T Expected Optimal Selection on the PRAM
%D December 03, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K parallel algorithm, selection, parallel random access machine (PRAM), expected value, variance, Chebyshev's Inequality
%Y F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
%X The Selection Problem is the following:  Given 
a totally ordered set $S$ of $n$ items 
and an integer $k$ such that $0 < k \leq n$, find the 
$k$-th smallest member of $S$. A general algorithm 
for a PRAM using optimal $\Theta(n)$ cost is not currently 
known.  In this paper, we show that if the input set $S$ is 
uniformly (randomly) distributed on an interval $[a,b]$, then 
the Selection Problem may be solved by an algorithm with the 
following properties:   
a) The expected cost is an optimal $\Theta(n)$.   
b) The worst-case cost is $\Theta(n \log^{(2)} n)$, which matches that of 
the most efficient algorithm in the literature~\cite{JaJa}.