**Reference**:- Mihai Pǎtraşcu and Erik D. Demaine, “Tight Bounds for the Partial-Sums Problem”, in
*Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)*, New Orleans, Louisiana, January 11–13, 2004, pages 20–29. **Abstract**:-
We close the gaps between known lower and upper bounds for the
online partial-sums problem in the RAM and group models of
computation. If elements are chosen from an abstract group, we prove
an Ω(lg
*n*) lower bound on the number of algebraic operations that must be performed, matching a well-known upper bound. In the RAM model with*b*-bit memory registers, we consider the well-studied case when the elements of the array can be changed additively by δ-bit integers. We give a RAM algorithm that achieves a running time of Θ(1 + lg*n*/ lg (b/δ)) and prove a matching lower bound in the cell-probe model. Our lower bound is for the amortized complexity, and makes minimal assumptions about the relations between*n*,*b*, and δ. The best previous lower bound was Ω(lg*n*/ (lg lg*n*+ lg*b*)), and the best previous upper bound matched only in the special case*b*= Θ(lg*n*) and δ =*O*(lg lg*n*). **Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (398k), gzipped PostScript (179k), and PDF (174k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DynamicConnectivity_SICOMP (Logarithmic Lower Bounds in the Cell-Probe Model)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.