why does accessing an element in an array take constant time?

Question

Lets say I have an array as:

int a[]={4,5,7,10,2,3,6}

when I access an element, such as a[3], what does actually happen behind the scenes? Why do many algorithm books (such as the Cormen book...) say that it takes a constant time?

(I'm just a noob in low-level programming so I would like to learn more from you guys)

Solution 1

Just to be complete, "what structure is accessed in linear time?" A Linked List structure is accessed in linear time. To get the n element you have to travel through n-1 previous elements. You know, like a tape recorder or a VHS cassette, where to go to the end of the tape/VHS you had to wait a long time :-)

An array is more similar to an hard disk: every point is accessible in "constant" time :-)

This is the reason the RAM of a computer is called RAM: Random Access Memory. You can go to any location if you know its address without traversing all the memory before that location.

Some persons told me that HD access isn't really in constant time (where by access I mean "time to position the head and read one sector of the HD"). I have to say that I'm not sure of it. I have googled around and I haven't found anyone speaking of it. I DO know that the time isn't linear, because it is still accessed randomly. In the end, if you think that HD access isn't constant enough for you (but then, what is constant? the access of the RAM? considering Cache, Prefetching, Data Locality and Compiler optimizations?), feel free to consider the sentence as An array is more similar to an USB disk stick: every point is accessible in "constant" time :-)

Solution 2

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 3

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

Solution 4

Because arrays are stored in memory sequentially. So actually, when you access array[3] you are telling the computer, "Get the memory address of the beginning of array, then add 3 to it, then access that spot." Since adding takes constant time, so does array access!

Solution 5

"constant time" really means "time that doesn't depend on the 'problem size'". For the 'problem' "get something out of a container", the 'problem size' is the size of the container.

Accessing an array element takes basically the same amount of time (this is a simplification) regardless of the container size, because a fixed set of steps is used to retrieve the element: its location in memory (this is also a simplification) is calculated, and then the value at that location in memory is retrieved.

A linked list, for example, can't do this, because each link indicates the location of the next one. To find an element you have to work through all the previous ones; on average, you'll work through half the container, so the size of the container obviously matters.

View more solutions