IMI-BAS
 

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

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, 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.
URI: http://hdl.handle.net/10525/728
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! DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback