Amortized Analysis for Addition of $n$ numbers

Question

How can we add n positive integers with binary expansion $l_1$, $l_2$,...$l_n$ bits so that the total complexity is $O (\sum l_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity using amortized analysis (the potential method)?

I know the elementary school addition of 2 numbers of length $s$ and $r$ is $O(r+s)$ and hence, the addition of n integers is $O(\sum l_i)$. However, what potential function would you use to prove that bound? I don't seem to have any intuition on that... Maybe use a function similar to the standard binary counter example (number of 1's in the binary representation of the number)..?

Answer 1

You should be slightly more careful in your argument. Let the actual numbers you are adding be $x_1,\ldots,x_n > 0$, where $\ell_i = \lfloor \log_2 x_i \rfloor + 1$. The complexity of adding two numbers $x,y>0$ is $O(\log(x+y))$. In our case, assuming we are doing the addition sequentially, the numbers we are adding are $x_i$ and $x_1 + \cdots + x_{i-1}$, for $i=2,\ldots,n$. Therefore the entire complexity is $$ O\big(\sum_{i=2}^n \log (x_1 + \cdots + x_i)\big). $$ Suppose now that we arrange the numbers in non-decreasing order $x_1 \leq x_2 \leq \cdots \leq x_n$. Then $$ \sum_{i=2}^n \log (x_1 + \cdots + x_i) \leq \sum_{i=2}^n \log (ix_i) \leq n\log n + \ell_1 + \cdots + \ell_n. $$ This is tight (up to constant factors) when all $\ell_i$ are equal. In particular, when adding $1$ to itself in this fashion, the complexity is $O(n\log n)$ rather than $O(n)$.

Can you think of a better way?

Answer 2

If the $i$-th number has $1$'s in bits $j_1, j_2, \dotsc$ (counted from the right), you can implement adding that number to the sum as stepping a counter once with each stepwidth $2^{j_1}, 2^{j_2}, \dotsc$. For this implementation, adapting the analysis for the standard binary counter should be straightforward. (See also here.)