Parallel Algorithms: Difference between revisions
| Line 166: | Line 166: | ||
E.g. | E.g. | ||
* Algo 1 runs in <math>O(\log n)</math> iterations each taking <math>O(\log | * Algo 1 runs in <math>O(\log n)</math> iterations each taking <math>O(\log n)</math> time and <math>O(n)</math> work. Each iteration reduces the size to (3/4)m. | ||
* Algo 2 runs in <math>O(\log n)</math> time and <math>O(n\log n)</math> work. | * Algo 2 runs in <math>O(\log n)</math> time and <math>O(n\log n)</math> work. | ||
* Run Algo 1 for <math>O(\log \log n)</math> rounds then run algo 2. | * Run Algo 1 for <math>O(\log \log n)</math> rounds then run algo 2. | ||