5,337
edits
Parallel Algorithms: Difference between revisions
→Maximum Finding
| Line 264: | Line 264: | ||
Given an array A=A(1),...,A(n), find the largest element in the array<br> | Given an array A=A(1),...,A(n), find the largest element in the array<br> | ||
===Constant time, <math>O(n^2)</math> Work=== | |||
* Compare every pair of elements in A[1...n] | * Compare every pair of elements in A[1...n] | ||
<pre> | <pre> | ||
| Line 279: | Line 279: | ||
</pre> | </pre> | ||
===<math>O(\log \log n)</math> time and <math>O(n\log \log n)</math> work algorithm=== | |||
* Split A into <math>\sqrt{n}</math> subarrays | * Split A into <math>\sqrt{n}</math> subarrays | ||
* Find the max of each subarray recursively | * Find the max of each subarray recursively | ||
| Line 289: | Line 289: | ||
* <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. | * Step 1: Partition into blocks of size <math>\log \log n</math>. Then we have <math>n/ \log \log n</math> blocks. | ||
| Line 296: | Line 296: | ||
* Step 2: Apply doubly log algorithm to <math>n / \log \log n</math> maxima. | * 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. | ** <math>O(\log \log n)</math> time and <math>O(n)</math> work. | ||
===Random Sampling=== | |||
==Resources== | ==Resources== | ||