Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/728

 Title: Matricial Model for the Study of Lower Bounds Authors: Joaquin Erviti, JoseToni, Adriana Keywords: Zero-One MatricesLower BoundsMatrix Equations Issue Date: 2006 Publisher: Institute of Information Theories and Applications FOI ITHEA Abstract: Let V be an array. The range query problem concerns the design of data structures for implementing the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower bound is near optimal – in terms of asymptotic complexity. URI: http://hdl.handle.net/10525/728 ISSN: 1313-0463 Appears in Collections: Volume 13 Number 1

Files in This Item:

File Description SizeFormat