In one of the stack overflow answers as to why ArrayList.get is O(1) and not O(n)
The responder said that ArrayList was backed by an array and a
Arrays are laid sequentially in memory. This means, if it is an array of integers that uses 4 bytes each, and starts at memory address 1000, next element will be at 1004, and next at 1008, and so forth. So, if I want the element at position 20 in my array, the code in
get() will have to compute:
1000 + 20 * 4 = 1080
to have the exact memory address of the element. Well, RAM memory got their name of Random Access Memory because they are built in such way that they have a hierarchy of hardware multiplexers that allow them to access any stored memory unit (byte?) in constant time, given the address.
Thus, two simple arithmetic and one access to RAM is said to be O(1).