TIGHT COMPLEXITY BOUNDS FOR PARALLEL COMPARISON SORTING.

Noga Alon, Yossi Azar, Uzi Vishkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

The time complexity of sorting n elements using p greater than equivalent to n processors on L. G. Valiant's (1975) parallel comparison tree model is considered. It is shown that this time complexity is THETA (log n/log(1 plus p/n)). For every fixed time k it is shown that OMEGA (n**1** plus **1 **/ **k ) comparisons are required and that there exists a randomized algorithm for comparison sort in time k with an expected number of O(n**1** plus **1 **k comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. It is shown that 'approximate sorting' in time 1 requires asymptotically more than n log n processors.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages502-510
Number of pages9
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - 1986
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'TIGHT COMPLEXITY BOUNDS FOR PARALLEL COMPARISON SORTING.'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Azar, Y., & Vishkin, U. (1986). TIGHT COMPLEXITY BOUNDS FOR PARALLEL COMPARISON SORTING. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 502-510). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1986.57