5,337
edits
Parallel Algorithms: Difference between revisions
→Random Sampling
| Line 298: | Line 298: | ||
===Random Sampling=== | ===Random Sampling=== | ||
Maximum finding in <math>O(1)</math> time and <math>O(n)</math> work with very high probability | |||
* Step 1: Using aux array B of size <math>b^{7/8}</math>. Independently fill with random elements from A | |||
* Step 2: Find the max <math>m</math> in array B in <math>O(1)</math> time and <math>O(n)</math> work | |||
** Last 3 pulses of the recursive doubly-log time algorithm: | |||
** Pulse 1: B is partitioned into <math>n^{3/4}</math> blocks of size <math>n^{1/8}</math> each. Find the max of each block. | |||
** Pulse 2: <math>n^{3/4}</math> maxima are partitioned into <math>n^{1/2}</math> blocks of size <math>n^{1/4}</math> each. | |||
** Pulse 2: Find the max m of <math>n^{1/2}</math> maxima in <math>O(1)</math> time and <math>O(n)</math> work. | |||
* Step 3: While there is an element larger than m, throw the new element into an array of size <math>n^{7/8}</math>. | |||
: Compute the maximum of the new array. | |||
;Complexity | |||
* Step 1 takes <math>O(1)</math> time and <math>O(n^{7/8})</math> work | |||
* Step 2 takes <math>O(1)</math> time and <math>O(n)</math> work | |||
* Each time Step 3 takes <math>O(1)</math> time and <math>O(n)</math> work | |||
* With high probability, we only need one iteration (see theorem below) so the time is <math>O(1)</math> and work is <math>O(n^{7/8})</math> | |||
====Theorem 8.2==== | |||
The algorithm find the maximum among <math>n</math> elements. | |||
With high probability it runs in <math>O(1)</math> time and <math>O(n)</math> work. | |||
The probability of not finishing in the above time is <math>O(1/n^c)</math>. | |||
==Resources== | ==Resources== | ||