Question

Let \(n\) be a power of 2. Show that \(n\) numbers can be added in \(\log n\) steps using a tree-connected network of \(n - 1\) processors.

Short answer

Let \(n - {2^k}\) for some positive integer k. Now consider a tree-connected network on a full binary tree with \(n - 1\) processors, which are denoted by the vertices of the tree.

Step-by-step solution

Binary tree

Let \(n = {2^k}\), for some positive integer \(k\). Now consider a tree-connected network on a full binary tree with \(n - 1\) processors, which are denoted by the vertices of the tree. Number of internal vertices of this tree is \(i = \frac{{(n - 1) - 1}}{2} = {2^{k - 1}} - 1\) and the number of leaves is \((n - 1) - i = {2^{k - 1}}\).

Sum of parent node

Each processor at a leaf can add two numbers and communicate the sum to its parent node. In this way, all the leaves can count the sums of \(l = {2^{k - 1}} = \frac{n}{2}\) pairs. Thus, we can group the n numbers into \(\frac{n}{2}\) pairs and calculate their sums and communicate them to the immediately above level of internal vertices. This process continues until the sum of all the n numbers be calculated at the processor at the root node, precisely after \(k = \log n\) steps.