5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Accelerating Cascades
| Line 163: | Line 163: | ||
Assume Algo A is a "reducing algorithm"<br> | Assume Algo A is a "reducing algorithm"<br> | ||
We start with Algo A until the size is below some threshold. Then we switch to Algo B. | We start with Algo A until the size is below some threshold. Then we switch to Algo B. | ||
E.g. | |||
* Algo 1 runs in <math>O(\log n)</math> iterations each taking <math>O(\log m)</math> math and <math>O(m)</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. | |||
* Run Algo 1 for <math>O(\log \log n)</math> rounds then run algo 2. | |||
** Total time is <math>O(\log n \log \log n)</math> and work is <math>O(n)</math> | |||
===Problem: Selection=== | ===Problem: Selection=== | ||