Why the running time complexity of (List

Question

From here I understood that the complexity of some static arr is O(1)

But for dynamic array the size is never set, so how the complexity will be constant? Even Oracle documentation says so.

static int count =  0;
public static void main(String[] args) {
    List.of(1, 2, 3, 4, 5).forEach(x -> count++); // Java-10
    System.out.println(count);
}

this code should determine the size of the list, if this runs for O(n) times then why

List.of(1, 2, 3, 4, 5).size();

is O(1)

because the size is stored internally somewhere in the list object. — OldProgrammer, Jul 15 '19 at 17:47
`List` is an interface, so whether `.size()` is O(1) or O(n) depends on the implementation. — Ivar, Jul 15 '19 at 17:48
*"But for dynamic array"* There is no such thing as a *dynamic array* in Java. Arrays always have a fixed size. — Andreas, Jul 15 '19 at 18:27

score 4 · Answer 1 · answered Jul 15 '19 at 17:49

4

As per, for example, here, ArrayList will store the current size as to make it immediately available. Other lists would be similar, as it's a common optimization. (Eg. LinkedList)

answered Jul 15 '19 at 17:49

Alex Hart

1,663
12
15

score 4 · Answer 2 · answered Jul 15 '19 at 17:59

4

While forming the List the time complexity is not O(1). After list is formed the size is saved internally in the list. After that when we call List.size() it just return the saved size with time complexity O(1)

answered Jul 15 '19 at 17:59

kayesh parvez

323
1
2
9

score 3 · Accepted Answer · answered Jul 15 '19 at 18:37

You're specifically asking why List.of(1, 2, 3, 4, 5).size() is O(1).

While other answers have correctly said that implementations such as ArrayList and LinkedList explicitly store the lists size as a field of the list, that doesn't actually answer your question, because List.of(E... elements) doesn't use those implementations.

List.of(E... elements) is varargs, which means that internally it is actually List.of(E[] elements) and the compiler builds a fixed array for you. In your case, that array is exactly 5 in size.

Although the implementation is really different, building an immutable list, the E[] is turned into a list similarly to how Arrays.asList(T... a) does it, i.e. by wrapping the array in a List implementation that uses the array directly.

As such, the list size of very well known, because the size is the length of the backing array.

3 Answers3