Java – time complexity of iterating over array lists

I have an array list and I iterate In each iteration, I call get () to get an element, and if the item passes some conditions, I use add () to add it to the new array list

List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
    Item tocheck = items.get(i);
    if(tocheck meets some condition){
        lessItems.add(tocheck);
    }
}

I'm not sure about the time complexity here I call get () on all projects, which is O (n) Then I also call add () on all potential projects, so there is another o (n) I'm not sure about that

Solution

All the other answers are wrong

>The first loop of the iterative item list: the complexity is O (n) > insert each item at the end of the list lesstitems: in the normal array, it will be what others call o (n) But Java uses amortized array to implement ArrayList This means that the algorithm only costs amortized o (1) when inserting at the end of the array Or you can say O (1)

Therefore, the complexity of the code is: O (n) * amortization o (1) In short, it is O (n)

Another reference:

dynamic array

Additional note 1:

If the complexity inserted at the end of the array is O (n), the total complexity is O (n ^ 2), not o (2 * n) as mentioned in other answers Because the total complexity of the insert will be: 1 2 3... N = n * (n 1) / 2

Additional note 2:

As stated in the official document:

Additional note 3:

This is the logic of the growth method I obtained from the official JAVA source code:

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscIoUs code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscIoUs code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size,so this is a win:
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

As the source code says, when the program adds elements that make the size of the array larger than the current capacity, the array will grow The new size of the growth array will be:

int newCapacity = oldCapacity + (oldCapacity >> 1);

This is a trick to make insertion allocation o (1)