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<k\rangle$ written in binary.

Output: $\sum_{i<k}X_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<k$.

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

  • $\begingroup$ Nice observation! This is new to me. $\endgroup$
    – Sam Buss
    May 20, 2023 at 2:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.