Time Complexity for Java Arraylist

Time complexity for java ArrayList

An ArrayList in Java is a List that is backed by an array.

The get(index) method is a constant time, O(1), operation.

The code straight out of the Java library for ArrayList.get(index):

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

Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)

What is the time complexity of Java's ArrayList.sublist(startIndex, endIndex) method?

The sub-list is backed by the source list. There is no copy step, so the time complexity is O(1).

Time Complexity for Java ArrayList

The best resource is straight from the official API:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

time complexity for arraylist resizing java

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;
}

What is the time complexity of retainAll and removeAll of ArrayList in Java.

Assume that our ArrayList<T> has n elements, and Collection<?> has r elements.

The answer depends on the timing of c.contains(es[r]) check, as implemented in the subclass of Collection<?>:

• If c is another ArrayList<?>, then the complexity is, indeed, quadratic O(n*r), because c.contains(es[r]) is O(r)
• If c is a TreeSet<?> then the time complexity becomes O(n*log₂r), because c.contains(es[r]) is O(log₂r)
• If c is a HashSet<?> then the time complexity becomes O(n), because hash-based c.contains(es[r]) is O(1)

Why ArrayList add() and add(int index, E) complexity is amortized constant time? Why not O(1) for add(), O(n) for add(int index, E)?

In Oracle terms (which are implied tacitly) and speaking about List

• "add method" (synonym - "append method") always means boolean add(E)
• "insert method" always means boolean add(int index, E)

When Oracle writes

The add operation runs in amortized constant time, that is, adding n
elements requires O(n) time.

it means:

Complexity of a single boolean add(E) operation is amortized O(1).

It cannot be just O(1) asymptotic (always) because rarely we need to grow array capacity. This single add operation which is in fact a "create new bigger array, copy old array into it, and then add one element to the end" operation is O(n) asymptotic complexity, because copying the array when increasing List capacity is O(n), complexity of growing plus addding is O(n) [calculated as O(n) + O(1) = O(n)]. Without this capacity growing operation, add complexity would have been O(1), element is always added (appended) to the end of array (max index). If we "added" (= inserted) not to array end, we would need to move rightmost elements (with bigger indexes), and complexity for single such operation would have been O(n).

Now, for a single add operation asymptotic complexity is O(1) for add-without-increasing-capacity and O(n) for add-with-increasing-capacity (which happens very rare).

Amortized complexity of a single add operation is O(1). It reflects the fact that rare O(n) grow-and-add operations get "diluted" with much more numerous O(1) add-without-grow ones, so "on the average" single operation is O(1).

"Asymptotic complexity" of n add operations is O(n). But here we speak about complexity of n operations, not complexity of one operation. It is not a strict way to put it like this ("Asymptotic complexity"), but anyway. Amortized complexity of n operations is even less sense.

Finally, boolean add(int index, E) single operation complexity is always O(n). If it triggers grows, it is O(n) + O(n) [grow + insert], but 2*O(n) is same as O(n).

Time Complexity of Looping over an ArrayList and putting values in HashMap vs. just searching the ArrayList

For just one search there's no point in creating a HashMap, since the time it takes to build the HashMap would be linear (O(n)), which is the same time it takes to directly search the ArrayList.

Since creating the HashMap has some overhead beyond the time it would take to iterate over the ArrayList, a single search by directly iterating over the ArrayList should be faster than building the HashMap and then searching for some key (though asymptotically both operations should take the same time).

A HashMap is justified if you are going to use it multiple times. For example, if you perform n searches on an ArrayList of size n, it would take O(n^2) time (since each search would require O(n) time).

On the other hand, if you put the elements of the ArrayList in a Map and perform n searches on the Map, the running time would be O(n) (since each search would take expected constant time).

Space complexity of Java data structures

They are all O(N) in space usage under normal conditions. (So are all of the standard collection data structures, I think ...)

Of course, that doesn't tell you some important facts about how much space these data structures will use in practice. For example:

• An ArrayList or HashMaps space usage is not directly proportional to the list size. Both have a "double the size when full" strategy for some or all of their space utilization.

• In the best case, an ArrayList uses less space per element than a LinkedList, and a LinkedList uses less space per element than a HashMap.

And so on.

It is also difficult to quantify the worst case ... because there are certain usage patterns that can lead to an empty ArrayList or HashMap occupying a large amount of space. For these data structures, the space usage may be proportional to the maximum N value (so far) not the current N value.

• An ArrayList does not "give back" space when elements are removed.

• With a HashMap the space occupied by the chains can grow and shrink, but the hash array only grows.

What is the time complexity of the ArrayList.add method?

As explained in this answer, Oracle uses a confusing convention: when they mention the add method, they usually refer to the add(E element) method, whereas the void add​(int index, E element) is referred to as the insert method... The method name is indeed confusing, and so is the class name too.

---

Related Topics