5,323
edits
Parallel Algorithms: Difference between revisions
→Problem: Selection
| Line 209: | Line 209: | ||
*What we have: | *What we have: | ||
**Algorithm 1 has <math>O(\log n)</math> iterations. | **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> | ::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 | *Step 2: Apply algorithm 2 | ||
Total time is <math>O(\log^2 n)</math> and total work is <math>O(n)</math> | |||
===Informal Work-Depth (IWD)=== | ===Informal Work-Depth (IWD)=== | ||