Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2604.01012 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917377812201472 |
|---|---|
| author | Au, Andrew |
| author_facet | Au, Andrew |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01012 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space Au, Andrew Data Structures and Algorithms 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. |
| title | Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.01012 |