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