Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does parallelism factor in when deriving the computational complexity of a parallel algorithm?

Suppose I have a perfect binary tree $T$ with leaves numbered $1$ to $n$, and an algorithm $\operatorname{Sum}()$ that computes the sum $1 + 2 + \dotsb + n$ in this way:

$\operatorname{Sum}(T)=$

If $T$ is a leaf node $k$, return $k$. Otherwise,

  1. $a \leftarrow \operatorname{Sum}(\text{left subtree of }T)$
  2. $b \leftarrow \operatorname{Sum}(\text{right subtree of }T)$
  3. Return $a + b$.

The total number of additions performed is $2^0 + 2^1 + 2^2 + \dotsb + n/2$. However, if steps (1) and (2) are performed in parallel, is the computational complexity $O(\log n)$ instead?

share|improve this question

1 Answer 1

You (or the compiler) would have to rewrite the algorithm, but as long as you had at least $n/2$ processors and communication between them could be done in constant time, then the parallel version would indeed have running time $O(\log n)$, since all of the work at a given level could be done (in parallel) at the same time.

Added. If we're restricted to a fixed number, $k$, of processors we first observe that the top $k+1$ layers (consisting of $O(k)$ nodes) can be added in $O(\log k)$ steps in parallel, as I noted above. However, for a tree with $N>2^k$ nodes, that will still leave us with $O(N-2^k)$ additions to perform and we can only compute these in $O((N-2^k)/k)$ time in parallel. Consequently, it will take $O(\log k +(N-2^k)/k)=O(N)$ steps, in general, to sum the nodes in a tree of size $N$.

share|improve this answer
    
But don't we usually assume that we have a constant number of processors? Does that bottleneck affect the complexity? –  Herng Yi Jan 28 '13 at 13:20
    
For theoretical purposes, we don't necessarily assume a constant number of processors. In situations where the number of processors is fixed, then, yes, it makes a difference. I'll expand on my answer after I come back from my classes. –  Rick Decker Jan 28 '13 at 13:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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