Why is accessing any single element in an array done in constant time ( O(1) )?

Question

According to Wikipedia, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.

To me, what happens behind the scenes probably looks something like this:

a) The search is done linearly (e.g. I want to access element 5. I begin the search at index 0, if it's not equal to 5, I go to index 1 etc.) This is O(n) -- where n is the length of the array

b) If the array is stored as a B-tree, this would give O(log n)

I see no other approach.

Can someone please explain why and how this is done in O(1)?

Answer 1

An array starts at a specific memory address start. Each element occupies the same amount of bytes element_size. The array elements are located one after another in the memory from the start address on. So you can calculate the memory address of the element i with start + i * element_size. This computation is independent of the array size and is therefor O(1).

Answer 2

In theory elements of an array are of the same known size and they are located in a continuous part of memory so if beginning of the array is located at A memory address if you want to access any element you have to compute its address like this:

A + item_size*index so this is a constant time operation.

Answer 3

Accessing a single element is NOT finding an element whose value is x.

Accessing an element i means getting the element at the i'th position of the array.

This is done in O(1) because it is pretty simple (constant number of math calculations) where the element is located given the index, the beginning of the array and the size of each element.

RAM memory offers a constant time (or to be more exact, a bounded time) to access each address in the RAM, and since finding the address is O(1), and retrieving the element in it is also O(1), it gives you total of O(1).

Finding if an element whose value is x is actually Omega(n) problem, unless there is some more information on the array (sorted, for example).

Answer 4

Usually an array is organized as a continuous block of memory where each position can be accessed by means of an index calculation. This index calculation cannot be done in constant time for arrays of arbitrary size, but for reasons of addressable space, the numbers involved are bounded by machine word size, so an assumption of constant time is justified.

Answer 5

If you have array of Int's. Each int is 32 bit's in java . If you have for example 10 integers in java it means you allocate memory of 320 bits. Then computer know

0 - index is at memory for example - 39200

last index is at memory 39200 + total memory of your array = 39200+320= 39520

So then if you want to access index 3. Then it is 39200 + 32*3 = 39296.

It all depends how much memory your object takes which you store in array. Just remember arrays take whole block of memory.