Go backward to
Time Analysis
Go up to
Top
Go forward to
Minimum of n Values
Parallel Algorithm
Sequence of square operations.
Each square op. contains
$n3$
independent (min,
$+$
) operations that can be performed in parallel yielding
$n3$
results.
Each of the
$n2$
entries
$D(i,j)$
is a minimum of
$n$
values.
Complexity:
$log\; n$
square computations.
1 time step for all (min,
$+$
) operations.
$log\; n$
time to compute each of the
$n2$
minimums.
Parallel complexity
$O(log2n)$
Author:
Wolfgang Schreiner
Last modification: November 15, 1996