The average-case parallel complexity of sorting

DOI10.1016/0020-0190(89)90194-4zbMath0689.68045OpenAlexW1963533750MaRDI QIDQ582080

Ravi B. Boppana

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90194-4

zbMATH Keywords

sortingparallel algorithmslower boundsaverage-case complexitycomparison trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (4)

Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ Transition Function Complexity of Finite Automata ⋮ Parallel comparison merging of many-ordered lists

Cites Work

• A Mathematical Theory of Communication
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Parallelism in Comparison Problems

This page was built for publication: The average-case parallel complexity of sorting