Paper by Erik D. Demaine

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)