5,350
edits
Parallel Algorithms: Difference between revisions
→Complexity
| Line 212: | Line 212: | ||
* Step 1:<math>T=O(r),\;W=O(r)</math> per subarray. | * Step 1:<math>T=O(r),\;W=O(r)</math> per subarray. | ||
** Total: <math>T=O(r),\; W=O(n)</math> | ** Total: <math>T=O(r),\; W=O(n)</math> | ||
* Step 2: r computations each <math>T=O(\log(n/r)),\; W=O(n/r)</math> | * Step 2: <math>r</math> computations each <math>T=O(\log(n/r)),\; W=O(n/r)</math> | ||
** Total <math>T=O(\log n),\; W=O(n)</math> | ** Total <math>T=O(\log n),\; W=O(n)</math> | ||
* Step 3: <math>T=O(\log r),\; W=O(r)</math> | * Step 3: <math>T=O(\log r),\; W=O(r)</math> | ||