Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Array Subscripting Operations

We now address the question of accessing the elements of an array of data. In general, the elements of a one-dimensional array are stored in consecutive memory locations. Therefore, given the address of the first element of the array, a simple addition suffices to determine the address of an arbitrary element of the array:

Axiom  The time required for the address calculation implied by an array subscripting operation, e.g., a[i], is a constant, tex2html_wrap_inline57190. This time does not include the time to compute the subscript expression, nor does it include the time to access (i.e., fetch or store) the array element.

By applying Axiom gif, we can determine that the running time for the statement

y = a [i];
is tex2html_wrap_inline57192. Three operand fetches are required: the first to fetch a, the base address of the array; the second to fetch i, the index into the array; and, the third to fetch array element a[i].


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.