Accessing Elements - Really O(1)?

Question

It is said that an example of a O(1) operation is that of accessing an element in an array. According to one source, O(1) can be defined in the following manner:

[Big-O of 1] means that the execution time of the algorithm does not depend on the size of the input. Its execution time is constant.

However, if one wants to access an element in an array, does not the efficiency of the operation depend on the amount of elements in the array? For example

int[] arr = new int[1000000];
addElements(arr, 1000000); //A function which adds 1 million arbitrary integers to the array. 

int foo = arr[55]; 

I don't understand how the last statement can be described as running in O(1); does not the 1,000,000 elements in the array have a bearing on the running time of the operation? Surely it'd take longer to find element 55 than it would element 1? If anything, this looks to me like O(n).

I'm sure my reasoning is flawed, however, I just wanted some clarification as to how this can be said to run in O(1)?

Answer 1

Array is a data structure, where objects are stored in continuous memory location. So in principle, if you know the address of base object, you will be able to find the address of ith object.

addr(a[i]) = addr(a[0]) + i*size(object)

This makes accessing ith element of array O(1).

EDIT
Theoretically, when we talk about complexity of accessing an array element, we talk for fixed index i.
Input size = O(n)
To access ith element, addr(a[0]) + i*size(object). This term is independent of n, so it is said to be O(1).

How ever multiplication still depends on i but not on n. It is constant O(1).

Answer 2

The address of an element in memory will be the base address of the array plus the index times the size of the element in the array. So to access that element, you just essentially access memory_location + 55 * sizeof(int).

This of course assumes you are under the assumption multiplication takes constant time regardless of size of inputs, which is arguably incorrect if you are being very precise