Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there an extension or translation of Brent's theorem into asymptotics aside from big-$O$?

Brent's Theorem: source

Running time of a parallel algorithm with $p$ processors (say, $f(n,p)$), $W(n)$ Work complexity, and $S(n)$ Step complexity takes $\leq \frac{W(n)}{p} + S(n)$ time. The $\leq$ lets me use $O$ directly, but not $\Omega$. If it's also true, I'd be able to say something like:

$f(n,p) \in \frac{\Theta(W(n))}{p} + \Theta(S(n))$

It seems like it is true. Is it? I'd love to have a reference.

share|cite|improve this question
You're asking for a lower bound on the conversion of an algorithm into a parallel algorithm ? that is likely to be hard. – Suresh Venkat Feb 14 '13 at 18:29
The algorithm shouldn't need to be converted. I just want to know whether Big-Theta holds. – Kyle Feb 14 '13 at 19:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.