5,337
edits
Parallel Algorithms: Difference between revisions
→Work-optimal List Ranking
| Line 403: | Line 403: | ||
* Recurse on <math>A-S</math> until size is <math>\leq n/\log n</math>. Then use pointer jumping. | * Recurse on <math>A-S</math> until size is <math>\leq n/\log n</math>. Then use pointer jumping. | ||
* Add <math>S</math> back to <math>A-S</math> | * Add <math>S</math> back to <math>A-S</math> | ||
; Complexity | |||
With high probability: | |||
* <math>O(log n log log n) time</math> | |||
* <math>O(n)</math> work | |||
===Randomized Symmetry Breaking=== | ===Randomized Symmetry Breaking=== | ||