61

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)

Morez
  • 2,085
  • 2
  • 10
  • 33

8 Answers8

35

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).

Reed Copsey
  • 554,122
  • 78
  • 1,158
  • 1,373
  • 3
    And because `*(a+3)` is the same as `*(3+a)`, we can write `a[3]` also as `3[a]`, a fact invariably useful in IOCCC and the like. :-) – ShreevatsaR Sep 04 '11 at 07:36
  • @ShreevatsaR: Yes, but... writing `3[a]` doesn't have a lot of practical uses - but using `*(a+3)` is often useful in real-world scenarios... – Reed Copsey Sep 04 '11 at 07:40
  • Your explanation would even hold when the index that is used would be a variable, too. But since here it is a constant (`3`) all computation can even be done by the compiler before hand and at run time the program can access the memory directly. So in fact it is not only constant, but a really small one. – Jens Gustedt Sep 04 '11 at 08:27
26

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

user3013127
  • 261
  • 3
  • 2
21

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 :-)

Community
  • 1
  • 1
xanatos
  • 109,618
  • 12
  • 197
  • 280
  • 5
    hard disks are a bad example for a random access memory, because that's exactly what they aren't. Maybe use a USB stick or a solid-state disk as example instead? – blubb Sep 04 '11 at 07:41
  • Yes and no... Technically the "external" part of an HD is faster than the inner part, but we will ignore this. Accessing a file on the HD is done in constant time (or at least not in linear time). If you have one file on an HD or a million files on an HD, accessing one of them will take the same time (not exactly, but it's more a theoretical model than the phisical reality we live in :-) ). – xanatos Sep 04 '11 at 07:44
  • Can the -1 be explained? I rethought it a little. HD access time is in constant time. Given an HD you have a medium seek time. So seeking the beginning of a file will take that time. – xanatos Sep 04 '11 at 08:05
  • I did not downvote, but I suspect it is due to the claim that HD access is constant time. If the reading head of a HD is at 3 o'clock on the disc, the time it takes to read another sector is also influenced by the location of said sector. If it's at 9 o'clock it will take considerably longer than if it's adjacent to the sector under the reading head. After all, this is why a lot of fancy optimization strategies have been invented to speed up pseudo-random access on HDs. – blubb Sep 04 '11 at 08:25
  • When you read something off a spinning hard disk, you first seek to the right track, and then read part or all of the track. The seek time is variable, because it depends on where you start from. That makes hard disk not be accessible in constant time. –  Sep 04 '11 at 08:25
  • @Lars and when you seek something from RAM it could be in the Cache. This makes access to RAM not constant in time. The current position on the HD is an externality you can't consider. It's opaque from your POV. – xanatos Sep 04 '11 at 08:32
  • @tsubasa -- why is this marked as the accepted answer? It may well be interesting & informative but it's not answering your question head-on like, say, Phil's answer. – AAT Sep 04 '11 at 08:55
  • I'll add that (if I remember correctly) the clock of the memory is different than the clock of the CPU. So the number of cycles the CPU has to wait to read a piece of memory is variable. So even direct RAM access isn't really "in constant time". – xanatos Sep 04 '11 at 09:48
  • 2
    "Constant time" just means bounded by a constant, i.e. `O(1)`. Technically speaking any finite media has `O(1)` access time, but for a tape the constant is so bad and the scaling of time is such that it's more practical to treat it as if the tape were potentially infinite. For hard drives (assuming no damage and infinite retry loops) the access time is bounded very small and for practical purposes should be considered `O(1)`. – R.. GitHub STOP HELPING ICE Sep 04 '11 at 13:02
  • This answer doesn't answer the question. The question asks "Why is an array constant time?" and you basically said "because RAM is constant time". Obviously saying how RAM works would be too deep but, at the very least, you need to mention memory address arithmetic because thats simply how an array works and how it is constant time. – Lv99Zubat Feb 26 '17 at 19:44
  • @ImpalaTamer This response wasn't made to be the "main response". It was to be a "long comment", an add-on. At the time I wrote it (4 sep 7:37) there was already a good-enough response (Reed Copsey 4 Sep 7:34). I consider that to be the "real" response to the question. For this reason, my response starts with a "Just to be complete". – xanatos Feb 27 '17 at 07:11
  • The problem with this answer is that you didn't explain *why* arrays are constant access. I know constant access means you can go straight to part of them, but why can you do that with an array and not a linked list? why can't you do a memory offset from the first node of a linked list? Because it's not guaranteed to be contiguous memory? – temporary_user_name Mar 10 '17 at 01:33
9

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!

Phil
  • 706
  • 5
  • 6
  • 1
    Actually you add 3 multiplied by the size of array elements. – Matteo Sep 04 '11 at 08:14
  • 1
    Well yes, but this is one of those topics that takes a chapter to explain precisely. I was intentionally leaving out details to avoid information overload for a beginner. – Phil Sep 04 '11 at 08:22
8

"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.

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
4

Array is collection of similar types of data. So all the elements will take same amount of memory.Therefore if you know the base address of array and type of data it holds you can easily get element Array[i] in constant time using formula stated below:

int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];

Hence, its clearly visible you can get ith element in constant time if you know the base address and type of data it holds. Please visit this link to know more about array data structure.

Sunil Kumar Jha
  • 841
  • 1
  • 8
  • 11
3

An array is sequential, meaning that, the next element's address in the array is next to the present one's. So if you want to get 5th element of an array, you calculate the address of 5th element by summing up the base address of the array with 5. This direct address is now directly used to get the element at that address.

You may now further ask the same question here- "How does the computer knows/accesses the calculated address directly?" This is the nature and the principle of computer memory (RAM). If you are further interested in how RAM accesses any address in constant time, you can find it in any computer organization text or you can just google it.

nikhiltejadonkana
  • 81
  • 1
  • 5
3

If we know memory location that need to be accessed then this access is in constant time. In case of array the memory location is calculated by using base pointer, index of element and size of element. This involves multiplication and addition operation which takes constant time to execute. Hence element access inside array takes constant time.

Narendra Kalekar
  • 120
  • 1
  • 6