Bounds on Selection Networks
Andrew Chi-Chih Yao · SIAM Journal on Computing · 1980
We investigate the complexity of network selection by measuring it in terms of $U(t,N)$, the minimum number of comparators needed, and $T(t,N)$, the minimum delay time possible, for networks selecting the smallest t elements from a set of N inputs. New bounds on $U(t,N)$ and $T(t,N)$ are presented. In particular, the asymptotic forms of $U(t,N)$ and $T(t,N)$ are determined for any fixed t.