5,337
edits
Parallel Algorithms: Difference between revisions
→Maximum Finding
| Line 262: | Line 262: | ||
==Maximum Finding== | ==Maximum Finding== | ||
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] | |||
<pre> | |||
for i=1 to n pardo | |||
B(i) = 0 | |||
for 1 <= i,j <= n pardo | |||
if A(i) <= A(j) and i < j | |||
B(i) = 1 | |||
else | |||
B(j) = 1 | |||
for 1 <= i <= n pardo | |||
if B(i) == 0 | |||
A(i) is the max | |||
</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 | |||
* Find the max of each subarray recursively | |||
* Find the max of all subarrays in <math>O(n)</math> using the constant time algo | |||
Complexity | |||
* <math>T(n) \leq T(\sqrt{n}) + c_1</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> | |||
==Resources== | ==Resources== | ||