### 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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE |

Pages | 502-510 |

Number of pages | 9 |

ISBN (Print) | 0818607408, 9780818607400 |

DOIs | |

State | Published - 1986 |

Externally published | Yes |

### Publication series

Name | Annual 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

*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