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.