5,323
edits
Parallel Algorithms: Difference between revisions
→Work-optimal List Ranking
| Line 452: | Line 452: | ||
;Complexity | ;Complexity | ||
We get the same complexity for randomized and deterministic list ranking (see below)<br> | |||
Randomized has the complexity with high probability. | |||
*<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 | ||