An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in $Θ(\lg N)$ time under the comparison based model of computation.
12 pages

Keywords

Data Structures and Algorithms, Computational Complexity, Information Retrieval, E.1; F.1.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/107178

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0601081
 http://arxiv.org/abs/cs/0601081

Collections

arXiv