1984/01/01 by Uzi Vishkin · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Advanced Graph Theory Research #Binary logarithm #Conjecture #Randomized algorithm #Parallel algorithm #Computer science #Computation #Parallel computing #Time complexity #Deterministic algorithm #Log-log plot #Algorithm #Speedup #Combinatorics #Running time #Mathematics #Discrete mathematics
paper · doi:10.1145/800057.808686
openalex publication_date 1984/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an O(log n) time deterministic parallel algorithm that uses only n/log n processors.