time complexity for java arrayList remove(element)

Question

I was trying to graph the Time Complexity of ArrayList's remove(element) method. My understanding is that it should be O(N), however, its giving me a O(1). Can anyone point out what i did wrong here?? Thank you in advance.

   public static void arrayListRemoveTiming(){
    long startTime, midPointTime, stopTime;
    // Spin the computer until one second has gone by, this allows this
    // thread to stabilize;
    startTime = System.nanoTime();
    while (System.nanoTime() - startTime < 1000000000) {
    }
    long timesToLoop = 100000;
    int N;
    ArrayList<Integer> list = new ArrayList<Integer>();

    // Fill up the array with 0 to 10000
    for (N = 0; N < timesToLoop; N++)
        list.add(N);

    startTime = System.nanoTime();
    for (int i = 0; i < list.size() ; i++) {
        list.remove(i);

        midPointTime = System.nanoTime();
        // Run an Loop to capture other cost.
        for (int j = 0; j < timesToLoop; j++) {

        }
        stopTime = System.nanoTime();

        // Compute the time, subtract the cost of running the loop
        // from the cost of running the loop.

        double averageTime = ((midPointTime - startTime) - (stopTime - midPointTime))
                / timesToLoop;

        System.out.println(averageTime);
    }


}

Answer 1

The cost of a remove is O(n) as you have to shuffle the elements above that point "left" by one. If your test code is giving you O(1) then you're not measuring it properly :-)

The OpenJDK source, for example, has this:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

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

    return oldValue;
}

and the System.arraycopy is the O(n) cost for this function.

---

In addition, I'm not sure you've thought this through very well:

for (int i = 0; i < list.size() ; i++)
    list.remove(i);

This is going to remove the following elements from the original list:

0, 2, 4, 8

and so on, because the act of removing element 0 shifts all other elements left - the item that was originally at offset 1 will be at offset 0 when you've deleted the original offset 0, and you then move on to delete offset 1.

You would be better off with:

list.remove(0);

inside the loop.