ArrayList Get Operation O(1). How?

Question

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

      RangeCheck(index);

is what determined the constant time complexity instead of linear! I'm trying to wrap my head around this, won't ANY array have to at least a partial search over perhaps a %age of n fields in an array thus constituting somehow an O(n) search ( if the element being hunted for is in the n-1 position of the array - wont this be an O(n) search? Its still a one level for loop which I thought was O(n) complexity?

`ArrayList.get(int)` does not search. It returns directly the element addressed by the index supplied... Exactly like with an array - hence the name. (Also, I assume this is about Java). For a LinkedList, this would hold, though! — ppeterka, Sep 25 '13 at 17:48
Is that link supposed to go to the Ask Question page? What language are you talking about here? — Wooble, Sep 25 '13 at 17:48
@ppeterka66 you should add that as an answer. Wooble: Java. [ArrayList.get](http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#get%28int%29) — Jano, Sep 25 '13 at 17:52
The answer is easy, internal representation of ArrayList is an array.. so you have directly access by index!. — nachokk, Sep 25 '13 at 18:17
What is going to stir you up more, is that a HashMap, has O(1) put, get, and remove. — Cruncher, Sep 25 '13 at 18:28

lvella · Accepted Answer · 2017-07-21T15:36:36.760

22

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. Thus, 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 operations and one access to RAM is said to be O(1).

edited Jul 21 '17 at 15:36

answered Sep 25 '13 at 17:56

lvella

12,754
11
54
106

2

+1, really addresses the root of why this is O(1), instead of just working on the assumption that arrays are O(1). I would add that "Arrays are laid sequentially in memory" this fact is the reason why arrays have to have a fixed size. You can never be sure what memory is after that array. – Cruncher Sep 25 '13 at 18:18
As aside, I've always wondererd: Wouldn't memory access be O(bits in a memory address)? That is to say, a memory access on a 32-bit system should be faster than a 64-bit system? Surely the circuitry has to make at least 1 decision for each bit right? Also, memory is infact byte-addressable. – Cruncher Sep 25 '13 at 18:23
Well, as long as (bits in a memory address) remains constant, O(bits in a memory address) is still, by big-o mathematical definition, O(1)... But the hardware is indeed more complex, and all this is a simplification, there are much more layers and algorithms involved, including L1 cache, L2 cache, MMU and virtual address tables. – lvella Sep 25 '13 at 18:30
But the bits in a memory address is not constant. My system may have more than yours. It's always constant for the same system, but it's not generically constant. I'm aware of virtual addressing, and registers, and cache etc, but I'm talking about when a memory access has to actually take place, would it take longer on a 64-bit system(all other variables being equal)? – Cruncher Sep 25 '13 at 18:35
If memory was a big linked list, and I had to traverse the whole memory space to get to my piece of memory, you would say that: it's O(n) where n is the amount of memory. You wouldn't say: It's O(1), because the system always has the same amount of memory. – Cruncher Sep 25 '13 at 18:36
This is perfect! This is what I needed - wanted to tie in constant time O(1) access to the under-the-hood explanation. Others explained it great as well - this one gives me THE solid explanation as to the nuances that clarifies this query! Thank you! – user2796381 Sep 25 '13 at 18:37
@user2796381 in fact in C, if you have an `int[]`, then `intArray[3]` is that same thing as `*(intArray + 12)`. (I think that's the right syntax, my C is shaky) Also assuming a 32-bit system. It's actually `*(intArray + 3 * sizeof(int))` – Cruncher Sep 25 '13 at 18:43
list.get(index) is O(1). Now as per you logic for Int it know how many bytes it will consume and pointer can reach to the asked index. As ArrayList is heterogeneous then how it will calculate the memory location @ 20th index (If it contains different objects like Long , Integers , Short , String). – Rahul Saxena Oct 10 '21 at 07:28
@RahulSaxena Since this question is about Java's ArrayList, the answer is easy: every object is allocated on the heap, so ArrayList only stores pointers to the objects, which are fixed to either 4 or 8 bytes (for 32bit and 64bit JVMs, respectively). For other languages, such as std::vector from C++, where the objects are actually stored in the list, such lists are always homogeneous, and each list used by the program is specialized for its type at compilation time, so that the interval between objects is fixed. – lvella Oct 10 '21 at 14:45

score 14 · Answer 2 · edited Jun 22 '16 at 13:34

Posted as answer, as suggested:

ArrayList.get(int) does not search. It returns directly the element addressed by the index supplied... Exactly like with an array - hence the name.

ArrayList.get(int) source:

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

Where rangeCheck(int) is:

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

And elementData() is:

E elementData(int index) {
    return (E) elementData[index];
}

A Linked List would however have an O(n) get: it would have to step to the next element until the desired index is reached...

public E get(int index) {
    return entry(index).element;
}

Where entry(int) is (this is what makes it O(n)):

private Entry<E> More ...entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Entry<E> e = header;

    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

(Note: it is double linked list, so saves some time by selecting the endpoint that is closest to the desired result, but this is still O(n) )

Thank you! The memory association and the codewise breakup gives a 360 degree picture! — user2796381, Sep 25 '13 at 18:38

score 0 · Answer 3 · answered Sep 25 '13 at 17:53

Accessing a particular index in an array is a constant time operation, because it involves getting the base memory address from the array object, and accessing the memory at base address + index multiplied by size of element type. Since all of the elements in between are skipped, the access time is bound by a constant.

The ArrayList.get(int) method is a thin wrapper over a direct array access, so it is also bounded by a constant.

ArrayList Get Operation O(1). How?

3 Answers3

Linked