5,337
edits
Parallel Algorithms: Difference between revisions
→Maximum Finding
| Line 288: | Line 288: | ||
* <math>W(n) \leq \sqrt{n}W(\sqrt{n}) + c_2 n</math> | * <math>W(n) \leq \sqrt{n}W(\sqrt{n}) + c_2 n</math> | ||
* <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> time | |||
* Step 1: Partition into blocks of size <math>\log \log n</math>. Then we have <math>n/ \log \log n</math> blocks. | |||
** Apply serial linear time algorithm to find maximum of each block | |||
** <math>O(\log \log n)</math> time and <math>O(n)</math> work. | |||
* Step 2: Apply doubly log algorithm to <math>n / \log \log n</math> maxima. | |||
** <math>O(\log \log n)</math> time and <math>O(n)</math> work. | |||
==Resources== | ==Resources== | ||