Brent's Theorem

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

For an algorithm with work W and depth D, the time T_p on p (homogeneous?) processors observes: W/p <= T_p <= D + (W - D)/p

FIXME beautify and expand! Tie into PRAM and Work-Depth