Check out my first novel, midnight's simulacra!

Brent's Theorem

From dankwiki
Revision as of 04:23, 10 September 2009 by Dank (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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 Tp on p (homogeneous?) processors observes: W/p <= Tp <= D + (W - D)/p

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