Brent's Theorem

From dankwiki
Revision as of 00:23, 10 September 2009 by Dank (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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