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?


$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.

  • $\begingroup$ 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? $\endgroup$
    – Mika H.
    Oct 3 '13 at 15:00
  • $\begingroup$ 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 $\endgroup$
    – ees_cu
    Oct 3 '13 at 15:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.