Area complexity of merging

DOI10.1016/0304-3975(91)90179-6MaRDI QIDQ807018zbMATH OpenOpenAlexWikidataFDO

Authors Vladimír Palko, Ondrej Sýkora, Imrich Vrt'o

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90179-6

zbMATH Keywords

merging two sorted arraysVLSI algorithmsVLSI area complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Review text

The paper under review deals with the VLSI area complexity for merging two sorted arrays of k-bit integers. First, a lower bound is established for this problem: \(\theta(m(\log n-\log m+1))\) if \(k\geq \log n\), \(A=\{\theta(\min \{2^ k,m\}(| k-\log m| +1))\) for \(k\leq \log n\), where m and n are the sizes of the arrays with \(m\leq n\). Then, two optimal circuits corresponding to the two cases are described.

Recommendations

• scientific article; zbMATH DE number 17819
• Lower bounds for merging networks
• scientific article; zbMATH DE number 3894473
• scientific article; zbMATH DE number 1256659
• scientific article; zbMATH DE number 3915623

Cites work

• A minimum-area circuit for -selection
• Area-time lower-bound techniques with applications to sorting
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3911723 (Why is no real title available?)
• scientific article; zbMATH DE number 3940717 (Why is no real title available?)
• scientific article; zbMATH DE number 4026821 (Why is no real title available?)
• scientific article; zbMATH DE number 3894473 (Why is no real title available?)
• Minimum Storage Sorting Networks
• The Area-Time Complexity of Binary Multiplication

Cited in

(2)

• scientific article; zbMATH DE number 17819 (Why is no real title available?)
• scientific article; zbMATH DE number 3894473 (Why is no real title available?)

This page was built for publication: Area complexity of merging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q807018)