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

<p>Brent's Theorem: <a href="http://www.cs.unc.edu/~prins/Classes/633/Handouts/pram.pdf" rel="nofollow">source</a></p>

<p>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:</p>

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

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

CC BY-SA 3.0
2013-02-14T18:29:21.313Z
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
CC BY-SA 3.0
2013-02-14T19:33:15.410Z
The algorithm shouldn't need to be converted.  I just want to know whether Big-Theta holds.
Kyle
<dc.parallel-comp><asymptotics>
Big-Theta extension of Brent's Theorem?
Kyle
# Big-Theta extension of Brent's Theorem?

(Asked by: username_0 on 2013-02-14)

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

Brent's Theorem: [source](http://www.cs.unc.edu/~prins/Classes/633/Handouts/pram.pdf)

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.

**Tags:** dc.parallel-comp, asymptotics

> **Comments:**
> **username_1**: You're asking for a lower bound on the conversion of an algorithm into a parallel algorithm ? that is likely to be hard.  
> **username_0**: The algorithm shouldn't need to be converted.  I just want to know whether Big-Theta holds.  

---

## 0 answers

