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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.