An improved reliability bound of a probabilistic parallel integer sorting algorithm

Research output: Contribution to journalArticlepeer-review

Abstract

It is shown how one can improve the reliability bound of the parallel sorting algorithm of Rajasekaran and Sen (1992) [7] that sorts uniformly distributed integer keys on a CRCW Parallel Random Access Machine (PRAM). The probability of success improves to 1-2 -Ω(nloglogn/logn) from the previous bound of 1-2 -Ω(n/(lognloglogn)) while retaining the Õ(logn) time bound for sorting n uniformly distributed integers on n/logn processors.

Original languageEnglish (US)
Pages (from-to)976-979
Number of pages4
JournalInformation Processing Letters
Volume112
Issue number24
DOIs
StatePublished - Dec 31 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • Integer sorting
  • Parallel algorithms
  • Randomized algorithms
  • Uniformly distributed integers

Fingerprint

Dive into the research topics of 'An improved reliability bound of a probabilistic parallel integer sorting algorithm'. Together they form a unique fingerprint.

Cite this