Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.