The Library
The asymptotic complexity of merging networks
Tools
Tools
Tools
Miltersen, Peter Bro, Paterson, Michael S. and Tarui, Jun (1995) The asymptotic complexity of merging networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF
WRAP_cs-rr-216.pdf - Requires a PDF viewer. Download (286Kb) | Preview |
Abstract
Let M(m, n) be the minimum number of comparators in a comparator network that merges two ordered chains x1 <= x2 <= . . . <= xm and y1 <= y2 . . . <= yn, where n >= m. Batcher's odd-even merge yields the following upper bound: M(m, n) <= (m + n)/2. log2(m + 1) + O(n), e.g., M (n, n) <= n log2 n + O(n). Floyd (for M(n, n)), and then Yao and Yao (for M(m, n)) have shown the following lower bounds: M(m, n) >= n/2. log2 (m + 1); M (n, n) >= n/2. log2 n + O (n). We prove a new lower bound that matches the upper bound asymptotically: M (m, n) >= (m + n)/2. log2 (m + 1) - O (m), e.g., M (n, n) >= n log2 n - O (n). Our proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | System analysis | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 16 January 1995 | ||||
| Dates: |
|
||||
| Number: | Number 216 | ||||
| Number of Pages: | 10 | ||||
| DOI: | CS-RR-216 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 7141 (ESPRIT) | ||||
| Version or Related Resource: | Miltersen, P.B., Paterson, M.S. and Tarui, J. (1996). The asymptotic complexity of merging networks. Journal of the ACM, 43(1), pp. 147-165. | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
