In the book Distributed Computing: A Locality-Sensitive Approach by David Peleg, in chapter 3, Broadcast and convergecast, in section 3.4.2 Global function computation, examples are given for global computation of functions. I can't understand the first example, of addition:

Example 1: Addition

Suppose that the function $f$ represents addition. Note that if the inputs are $m$-bit integers, then $f\left(\mathcal{Y}\right)$ can be represented in $O\left(m\log{n}\right)$ bits for any $\mathcal{Y}\subseteq\mathcal{X}$. Therfore, the message and time cmplexities of the convergecast process performed by Procedure CONVERGE($+$) on the tree $T$ are $O\left(nm\right)$ and $O\left(Depth\left(T\right){\cdot}m\right)$, respectivly.

What I don't understand is why the complexities are $O\left(nm\right)$ and $O\left(Depth\left(T\right){\cdot}m\right)$ and not just the "normal" $O\left(n\right)$ and $O\left(Depth\left(T\right)\right)$. I realize that this is comehow related the $m$-bit representation of the integers iputs. Why is there a factor $m$ in the complexities?


Your Answer

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

Browse other questions tagged or ask your own question.