Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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)

[img]
Preview
PDF
WRAP_cs-rr-216.pdf - Requires a PDF viewer.

Download (286Kb) | Preview

Request Changes to record.

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:
DateEvent
16 January 1995Completion
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:
  • Organisation
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us