|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
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,. 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 
,
we can determine that the running time for the statement
y = a[i];is
.
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].
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.