A minimum-area circuit for \(\ell\)-selection (Q1092661)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A minimum-area circuit for \(\ell\)-selection |
scientific article |
Statements
A minimum-area circuit for \(\ell\)-selection (English)
0 references
1987
0 references
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))\).
0 references
area-time complexity
0 references
selection of the \(\ell th\) smallest element
0 references
minimum-area computation
0 references
VLSI algorithms
0 references
lower bounds
0 references
VLSI circuits
0 references
\(\ell \)-selection
0 references