5,323
edits
Parallel Algorithms: Difference between revisions
→Work-optimal List Ranking
| Line 456: | Line 456: | ||
*<math>O(\log (n) \log \log (n))</math> time | *<math>O(\log (n) \log \log (n))</math> time | ||
*<math>O(n)</math> work | *<math>O(n)</math> work | ||
Using a parallel prefix-sum algorith which runs in <math>O(\log n/\log \log n)</math> time, | |||
we can get list ranking in <math>O(\log n)</math> time and <math>O(n)</math> work. | |||
===Randomized Symmetry Breaking=== | ===Randomized Symmetry Breaking=== | ||