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

c arrays time constants complexity-theory
user188276 picture user188276 · Sep 4, 2011 · Viewed 20.7k times · Source

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)

Answer

Reed Copsey picture Reed Copsey · Sep 4, 2011

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

Related questions

How do I determine the size of my array in C?

How do I determine the size of my array in C? That is, the number of elements the array can hold?

Read More
How to initialize all members of an array to the same value?

I have a large array in C (not C++ if that makes a difference). I want to initialize all members of the same value. I could swear I once knew a simple way to do this. I could use memset() …

Read More
How do I create an array of strings in C?

I am trying to create an array of strings in C. If I use this code: char (*a[2])[14]; a[0]="blah"; a[1]="hmm"; gcc gives me "warning: assignment from incompatible pointer type". What is the correct way to do this? edit: …

Read More