5,337
edits
Parallel Algorithms: Difference between revisions
→O(\log \log n) time and O(n) time
| Line 295: | Line 295: | ||
* <math>T(n) = O(\log \log n)</math>, <math>W(n) = O(n\log \log n)</math> | * <math>T(n) = O(\log \log n)</math>, <math>W(n) = O(n\log \log n)</math> | ||
===<math>O(\log \log n)</math> time and <math>O(n)</math> | ===<math>O(\log \log n)</math> time and <math>O(n)</math> work=== | ||
* Step 1: Partition into blocks of size <math>\log \log n</math>. Then we have <math>n/ \log \log n</math> blocks. | * Step 1: Partition into blocks of size <math>\log \log n</math>. Then we have <math>n/ \log \log n</math> blocks. | ||