5,337
edits
Parallel Algorithms: Difference between revisions
→Problem: Selection
| Line 173: | Line 173: | ||
; Accelerating Cascades | ; Accelerating Cascades | ||
* Algorithm 1 has <math>O(\log n)</math> iterations. | * What we have: | ||
: Each iteration reduces a size m instance in <math>O(\log m)</math> time and <math>O(m)</math> work to an instance of size <math>\leq 3m/4</math> | ** Algorithm 1 has <math>O(\log n)</math> iterations. | ||
:: Each iteration reduces a size m instance in <math>O(\log m)</math> time and <math>O(m)</math> work to an instance of size <math>\leq 3m/4</math> | |||
** Algorithm 2 runs in <math>O(\log n)</math> time and <math>O(n \log n)</math> work. | |||
* Step 1: Use algo 1 to reduce from n to <math>n / \log n</math> | * Step 1: Use algo 1 to reduce from n to <math>n / \log n</math> | ||
* Step 2: Apply algorithm 2 | |||
===Informal Work-Depth (IWD)=== | ===Informal Work-Depth (IWD)=== | ||