Calculation of Recursive Spawning 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.