Average complexity of deterministic and randomized parallel comparison-sorting algorithms

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

In practice, the average time of (deterministic of randomized) sorting algorithms seems to be more relevant than the worst-case time of deterministic algorithms. Still, the many known complexity bounds for parallel comparison sorting include no nontrivial lower bounds for the average time required to sort by comparison n elements with p processors (via deterministic or randomized algorithms). We show that for p≥n this time is Θ(log n/log(1+p/n)) (it is easy to show that for p≤n the time is Θ(n log n/p)=Θ(log n/(p/n)). Therefore even the average-case behavior of randomized algorithms is not more efficient than the worst-case behavior of deterministic ones.

Original languageEnglish (US)
Pages (from-to)1178-1192
Number of pages15
JournalSIAM Journal on Computing
Volume17
Issue number6
DOIs
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Average complexity of deterministic and randomized parallel comparison-sorting algorithms'. Together they form a unique fingerprint.

  • Cite this