Technical Reports

The ICICS/CS Reading Room


UBC CS TR-90-12 Summary

Selection Networks, May 1990 Nicholas Pippenger

We establish an upper bound asymptotic to $2n \log_{2}n$ for the number of comparators required in a network that classifies $n$ values into two classes each containing $n/2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n/2) \log_{2}n.$)


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.