In an ArrayList if an element is removed at index 0 using remove(), then what will be the time complexity?

Viewed 48

I think that the time complexity will be O(1). Since there are no loops in the declaration of remove method. Please let me know if my approach to think about time complexity is incorrect.

Declaration of remove():

public synchronized E remove(int index) 
{
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}
1 Answers

This is incorrect. There's a loop there, even if you don't see the word "for" or "while." (Hint: what are the time complexities of all the functions called inside that function?)

Related