5,337
edits
Parallel Algorithms: Difference between revisions
→Theorem 8.2
| Line 319: | Line 319: | ||
With high probability it runs in <math>O(1)</math> time and <math>O(n)</math> work. | With high probability it runs in <math>O(1)</math> time and <math>O(n)</math> work. | ||
The probability of not finishing in the above time is <math>O(1/n^c)</math>. | The probability of not finishing in the above time is <math>O(1/n^c)</math>. | ||
{{ hidden | Proof | | |||
See page 58 of the classnotes.<br> | |||
}} | |||
==Resources== | ==Resources== | ||