Paper by Erik D. Demaine
- 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.
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).
- The paper is 10 pages.
- 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.
These pages are generated automagically from a
Last updated May 4, 2022 by