CODEWITHSUNDEEP
javaarraylisttime-complexity
Ashley
Ashley

Reputation: 23

time complexity for arraylist resizing java

I know that the default size for arraylist is 10, and that the arraylist automatically expands for additional items added.

What is the time complexity for the resizing/expansion?

is it similar to a normal array, where the items have to be copied over into the new larger array for O(n) time?

Upvotes: 2

Views: 1100

Answers (1)

Zabuzard
Zabuzard

Reputation: 25903

Overview

The time complexity for resizing is O(n).

It will create a new array with double the capacity and copy over each element from the original array into the new array. This requires a full iteration. Note that this can be optimized internally by the JVM though.

Amortized

Resizing is not needed often. In particular not for every add call. Hence, why it doubles the internal capacity. This gives room for a whole bunch of subsequent add-calls.

More formally, this yields the amortized complexity of O(1) for add, even though its regular complexity would be O(n) bound by the resize.

Details

You can see the source of this here (OpenJDK 17):

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (/* ... */) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // ...
    }
}

The preferred growth is oldCapacity >> 1, i.e. double the capacity. The actual part that costs you performance and gives you the O(n) is Arrays.copyOf(...).

This method is called primarily from this helper:

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

That is used by the main entry point add(E):

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

Upvotes: 2

Related Questions