Temporary complexity for java arrayList remove (element)

Question

I tried to draw the Time Complexity method of the ArrayList remove (element) method. I understand that this should be O (N), however, this gives me 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

First, you do not measure the complexity of this code. What you are doing is measuring (or trying to measure) performance. When you draw numbers (assuming they are correctly measured), you get a performance curve for a particular use case in a finite range of values ​​for your scaling variable.

This is not the same as a measure of computational complexity; that is, large O or the associated Bachmann-Landau notation . These are mathematical limits as the scaling variable tends to infinity.

And it's not just nitpick. It is very easy to build examples in which performance characteristics change markedly when N becomes very large.

What does it do when you evaluate performance over a range of values ​​and approach a curve to evaluate complexity.

---

The second point is that the complexity of ArrayList.remove(index) sensitive to the value of index , as well as to the length of the list.

• "Advertised" O(N) complexity for medium and worst cases.

• At best, the complexity is actually O(1) . Indeed!

  This happens when you delete the last item in a list; those. index == list.size() - 1 . This can be done with zero copy; look at the code that @paxdiablo included in your answer.

---

Now to your question. There are a number of reasons why your code may give incorrect measurements. For example:

• You do not take into account JIT compilation overhead and other JVM warm-up effects.

• I see places where the JIT compiler can potentially optimize entire loops.

• The way you measure time is strange. Try to see it as algebra ... and simplifying.

    ((midPoint - start) - (stop - midPoint)) / count; 

  The term midPoint disappears ....

• You remove only half of the items from the list, so you only measure the range from 50,000 to 100,000 of the zoom variable. (And I expect that you then plot against the scaling variable, i.e. you draw f (N + 5000) against N.

• The time intervals that you measure may be too small to resolve the clock on your computer. (Read the javadocs for nanoTime() to find out what resolution it guarantees.)

Answer 2

The cost of remove is O(n) , since you need to shuffle the elements above this point “left” by one. If your test code gives you O(1) , you will not measure it correctly :-)

An OpenJDK source, for example, has the following:

 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 System.arraycopy is the O(n) cost for this function.

---

Also, I'm not sure if you understood this well:

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

This will remove the following items from the original list:

 0, 2, 4, 8 

etc., because the action of deleting element 0 shifts all other elements to the left - the element that was originally with offset 1 will be at offset 0 when you deleted the original offset 0, and then move to remove offset 1.

You would be better off:

 list.remove(0); 

inside the loop.

Answer 3

remove(int) removes the element at the i-th index, which is O (1)

You probably want remove( Object ) , which is O (N), you will need to call remove(Integer.valueOf(i))

it would be more obvious if your list had no items in order