BulDML at Institute of Mathematics and Informatics >
International Journal ITA >
2006 >
Volume 13 Number 1 >

Please use this identifier to cite or link to this item:

Title: Matricial Model for the Study of Lower Bounds
Authors: Joaquin Erviti, Jose
Toni, Adriana
Keywords: Zero-One Matrices
Lower Bounds
Matrix 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.
ISSN: 1313-0463
Appears in Collections:Volume 13 Number 1

Files in This Item:

File Description SizeFormat
ijita13-1-p09.pdf84.03 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License