why does accessing an element in an array take constant time?
Solution 1:
The array, effectively, is known by a memory location (a pointer). Accessing a[3]
can be found in constant time, since it's just location_of_a+3*sizeof(int).
In C, you can see this directly. Remember, a[3]
is the same as *(a+3)
- which is a bit more clear in terms of what it's doing (dereferencing the pointer "3 items" over).
Solution 2:
an array of 10 integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, … 2036, so that the element with index i has the address 2000 + 4 × i. this process take one multiplication and one addition .since these two operation take constant time.so we can say the access can be perform in constant time