2
$\begingroup$

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)..?

$\endgroup$
  • $\begingroup$ What is $\ell_i$? Is it the number of bits in the binary representation (e.g. always 32), or is it the number of ones in the binary representation, or is it the number of bits required to represent $i$, $O(\log_2 i)$, or something else? $\endgroup$ – Joe Mar 25 '14 at 18:24
1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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