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