Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
This work addresses a theoretical lower bound problem for algorithms in computational complexity, focusing on a toy problem to demonstrate proof techniques, making it incremental in nature.
The paper tackled the problem of computing the sum-exclude-self for unsigned integer arrays under sublinear space constraints, proving that any algorithm must perform at least two linear passes over the input, with a total of at least 2n - 1 - floor(t/d) element reads, where t is the working memory size.
We prove that any algorithm computing the sum-exclude-self of an unsigned $d$-bit integer array of length $n$ under sublinear space must perform two linear passes over the input. More precisely, the algorithm must read at least $n-1$ input elements before any output cell receives its final value, and at least $n - \lfloor t/d \rfloor$ additional elements thereafter, where $t = o(nd)$ bits is the working memory size. This gives a total of $2n - 1 - \lfloor t/d \rfloor$ element reads. A trivial modification of the standard two-pass algorithm achieves this bound exactly for all practical input sizes. The proof uses this toy problem as a worked example to demonstrate the choke-point technique for proving sublinear-space lower bounds.