<p>$T_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split each half in two chunks each. And so on until you have one iteration on each chunk, so you can compute it in $iter_\infty (i)$ time. Given that you have an infinite number of processors you can recruit twice the number of processors on each new level of this recursion, so each level can be executed in $O(1)$, but still you need to executed each level after the other. In order to have $n$ iterations (leaf on the recursion tree) you will need $O(\log n)$ levels.</p>

CC BY-SA 3.0
2013-10-03T15:00:08.137Z
`So, at first, one processor split the number of iterations in two` I think that's where my question comes in. Couldn't you split it into $n$ instead of two?
Mika H.
CC BY-SA 3.0
2013-10-03T15:26:09.657Z
How do you assign $n$ task in one step? You need to recruit the new threads and assign a task to each one. You cannot just summon $n$ thread out of nowhere. Iterate over this creation in the first step will be $O(n)$ rather than $O(\log n)$ with the recursion
ees_cu
CC BY-SA 3.0
2013-10-03T13:45:03.940Z
2013-10-03T13:50:22.650Z
2013-10-03T13:50:22.650Z
ees_cu
<p>I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following:</p>

<blockquote>
  <p>We must also account for the overhead of recursive spawning when analyzing the
  span of a parallel-loop construct. Since the depth of recursive calling is logarithmic in the number of iterations, for a parallel loop with $n$ iterations in which the $i$th iteration has span $iter_{\infty}(i)$, the span is $$T_\infty(n)=\Theta(\lg n)+\max_{1\leq i\leq n}iter_\infty(i).$$</p>
</blockquote>

<p>I agree that if there are a fixed number of processor, say $2$, then the depth is indeed $\log n$. But what if there are a huge number of processors, so that it can handle even large values of $n$? Wouldn't the depth of recursive calling be $\Theta(1)$ in that case?</p>

<time-complexity><dc.parallel-comp>
Calculation of Recursive Spawning
Mika H.
# Calculation of Recursive Spawning

(Asked by: username_0 on 2013-10-03)

I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following:

> We must also account for the overhead of recursive spawning when analyzing the
> span of a parallel-loop construct. Since the depth of recursive calling is logarithmic in the number of iterations, for a parallel loop with $n$ iterations in which the $i$th iteration has span $iter\_{\infty}(i)$, the span is $$T\_\infty(n)=\Theta(\lg n)+\max\_{1\leq i\leq n}iter\_\infty(i).$$

I agree that if there are a fixed number of processor, say $2$, then the depth is indeed $\log n$. But what if there are a huge number of processors, so that it can handle even large values of $n$? Wouldn't the depth of recursive calling be $\Theta(1)$ in that case?

**Tags:** time-complexity, dc.parallel-comp

---

## 1 answers

### Answer by username_1 on 2013-10-03. Score: 1 | Accepted answer

$T\_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split each half in two chunks each. And so on until you have one iteration on each chunk, so you can compute it in $iter\_\infty (i)$ time. Given that you have an infinite number of processors you can recruit twice the number of processors on each new level of this recursion, so each level can be executed in $O(1)$, but still you need to executed each level after the other. In order to have $n$ iterations (leaf on the recursion tree) you will need $O(\log n)$ levels.

> **Comments:**
> **username_0**: `So, at first, one processor split the number of iterations in two` I think that's where my question comes in. Couldn't you split it into $n$ instead of two?  
> **username_1**: How do you assign $n$ task in one step? You need to recruit the new threads and assign a task to each one. You cannot just summon $n$ thread out of nowhere. Iterate over this creation in the first step will be $O(n)$ rather than $O(\log n)$ with the recursion  

---

