A minimum-area circuit for \(\ell\)-selection (Q1092661)

We prove tight upper and lower bounds on the area of semelective, when- oblivious VLSI circuits for the problem of \(\ell\)-selection. The area required to select the \(\ell th\) smallest of n k-bit integers is found to be heavily dependent on the relative sizes of \(\ell\), k, and n. When \(\ell <2^ k\), the minimal area is \(A=\theta (\min \{n,\ell (k-\log \ell)\})\). When \(\ell \geq 2^ k\), then \(A=\theta (2^ k(\log \ell - k+1))\).