5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Pointer Jumping
| Line 394: | Line 394: | ||
Complexity: <math>O(\log n)</math> time and <math>O(n\log n)</math> work | Complexity: <math>O(\log n)</math> time and <math>O(n\log n)</math> work | ||
===Work-optimal List Ranking=== | |||
<pre> | |||
for i 1 <= i <= n pardo | |||
with equal probability R(i) = head or tail | |||
if R(i) == HEAD and R(next(i))==Tail | |||
s(i) = 0 | |||
else | |||
s(i) = 1 | |||
</pre> | |||
==Resources== | ==Resources== | ||