1
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But don't we usually assume that we have a constant number of processors? Does that bottleneck affect the complexity? $\endgroup$ Commented Jan 28, 2013 at 13:20
  • $\begingroup$ 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. $\endgroup$ Commented Jan 28, 2013 at 13:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.