# Can we do integer addition in linear time?

Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:

Input: A sequence of nonnegative integers $$\langle X_i:i written in binary.

Output: $$\sum_{i.

The size of the input is $$n=k+\sum_in_i$$, where $$n_i$$ is the length of $$X_i$$. Can we compute the sum in time $$O(n)$$ on a multi-tape Turing machine? (Or log-cost RAM, I guess. Not unit-cost RAM, which would trivialize the problem.) (This is not yet the question.)

The most stupid baseline algorithm is to use a second tape as an accumulator, and add the numbers to it one by one. Since all the intermediate sums have length $$O(n)$$, and addition of two integers is linear-time, this algorithm works in time $$O(nk)\subseteq O(n^2)$$.

It is a notorious example in amortized complexity that a binary counter can do $$n$$ increments in time $$O(n)$$ rather than the naïve bound $$O(n\log n)$$. This shows that the algorithm above works in linear time in the special case $$X_i=1$$ for all $$i.

I claim that this amortized analysis can be generalized to the full problem, showing that the baseline algorithm actually works in time $$O(n)$$; in particular, if $$t_i\ge n_i$$ denotes the last position visited when adding $$X_i$$ to the accumulator, then $$\sum_it_i\le2\sum_in_i$$. Thus, the stupid algorithm is not stupid at all, it is actually quite efficient!

Now, this looks like a basic result in algorithmic complexity, and surely must have been observed before. But unlike the special case of binary counters, I wasn't able to locate it in the literature.

Question: Is there a reference for the fact that the sum of a sequence of integers can be computed with $$O(n)$$ bit operations?

PS: I’ve written up the argument in arXiv:2306.08513 [cs.CC].

• Nice observation! This is new to me. May 20 at 2:12