The Library
The asymptotic complexity of merging networks
Tools
Miltersen, Peter Bro, Paterson, Michael S. and Tarui, Jun. (1996) The asymptotic complexity of merging networks. Journal of the ACM, Volume 43 (Number 1). pp. 147165. ISSN 00045411
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1145/227595.227693
Abstract
Let M(m, n) be the minimum number of comparators needed in a comparator network that merges m elements x(1) less than or equal to x(2) less than or equal to ... less than or equal to x(m) and n elements y(1) less than or equal to y(2) less than or equal to ... less than or equal to y(n), where n greater than or equal to m. Batcher's oddeven merge yields the following upper bound:
M(m,n) less than or equal to 1/2(m + n)log(2)m + O(n);
in particular,
M(n,n) less than or equal to n log(2)n + O(n).
We prove the following lower bound that matches the upper bound above asymptotically as n greater than or equal to m > infinity:
M(m,n) greater than or equal to 1/2(m + n)log(2)m  O(m);
in particular,
M(n,n) greater than or equal to 1/2 n log(2)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:  Journal Article  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Journal or Publication Title:  Journal of the ACM  
Publisher:  Association for Computing Machinery, Inc.  
ISSN:  00045411  
Official Date:  January 1996  
Dates: 


Volume:  Volume 43  
Number:  Number 1  
Number of Pages:  19  
Page Range:  pp. 147165  
Status:  Peer Reviewed  
Publication Status:  Published  
Version or Related Resource:  Miltersen, P.B., Paterson, M.S. and Tarui, J. (1995). The asymptotic complexity of merging networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report, 216)  
Related URLs:  
URI:  http://wrap.warwick.ac.uk/id/eprint/18594 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 