To the question of removing each Kth element from an arraylist in a circle , an answer was proposed :

import java.util.ArrayList; public class MyClass { public static void main(String[] args) { ArrayList <Integer> list1 = new ArrayList(); int n = 10; int k = 3; for (int i = 0; i<n; i++){ list1.add(i+1); } int pos =0; while (list1.size()!=1) { pos = (pos+k-1)%list1.size(); list1.remove(pos); } System.out.print(list1.get(0)); } }

This is a quadratic O (n²) algorithm, but apparently this is not obvious, since it leads to the following questions:

... where did you see n ^ 2 here? ... there is one while loop, which for each iteration "removes" one element, where is the square here?

How do popular Java implementations behave? Does the O (n) language specification guarantee behavior for ArrayList.remove(i) for an arbitrary index?

  • ru.stackoverflow.com/questions/568119#583973 - Nofate ♦
  • @Nofate: your link says the opposite (as guaranteed by O (n)). It confirms that ArrayList.remove(i) is O (n) operation, which for this algorithm leads to O (n²): n times deleted one element ( n*n ). It remains only to find the link to the language specification where O (n) is explicitly guaranteed for ArrayList.remove () - jfs
  • Yes, I somehow read the wrong question) - Nofate ♦
  • The @jfs link from zRrr is the API specification. The language specification (JVMLS) is more about syntax, the standard library is not included. - Nofate ♦
  • one
    @jfs The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add-on operation runs in amortized constant time, that is, adding n elements requires O (n) time. All of the other operations run in linear time. - Nofate ♦

2 answers 2

From the Java API Specification about ArrayList :

  • The operations size , isEmpty , get , set , iterator and listIterator are executed in constant time. The add operation is performed in O (1) amortized time, that is, n elements will be added in O (n) . All other operations are performed in linear time (roughly speaking).

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.

ArrayList.remove() belongs to the “other operations” category, therefore deleting one arbitrary element is O (n) operation. The cycle from the question one by one deletes the elements (total n deletions). Total: n * O (n) = O (n * n), that is, the algorithm presented in the question is quadratic.

  • To make the answer a quotation, it is worth mentioning explicitly how it affects the time complexity of the algorithm from the question: ArrayList.remove () belongs to the category “other operations”, therefore doubling one arbitrary element is O (n) operation. The cycle from the question one by one deletes the elements (total n deletions). Total: n * O(n) = O(n*n) that is, the algorithm presented in the question is quadratic. - jfs
  • @jfs as you say) - Nofate ♦
  • In fact, there is not quite n * O(n) , since in the first step the elements n , in the second n - 1 , ..., in the last 1. Therefore, the total number of operations does not exceed C * (n + (n - 1) + ... + 1) = C * n * (n + 1)/2 , which is still equal to O(n^2) . - VladD
  • @VladD: just in case: O(n * n) and O(n ^ 2) are the same (so that there are no different readings). O(n*n) == O(n*n/2) == O(C * n * n) , where C is a constant independent of n . Whatever the constant C is, the quadratic algorithm does not change it. - jfs
  • @jfs: I know. I after all also wrote the comment at the end: that all the same it is equal O(n^2) . - VladD

Good question, now I will explain what is the matter here. The fact is that the implementation of the ArrayList collection is based on an array. And as you know, a memory is allocated for an array in blocks, so access to an element is carried out in constant time - simply by its index. And it would be possible to finish this, if not for one BUT.
When an element is removed from an ArrayList , all elements after the id of the udible element in the array are shifted one position to the left. Now I will explain with an example. Source array:

 [1, 2, 3, 4, 5, 6]

We make .remove(3) and get this state:

 [1, 2, 4, 5, 6, 6]

After that, the last array index (last digit 6) vanishes.
The shift is performed using the native System.arrayCopy() method, which is not written in Java and works many times faster than normal manual element-by-element copying, however, its speed in Big O notation is estimated close to O (n).

For the case of LinkedList , which is based on a doubly linked list, although we delete by index, in any case we need to find this element before deleting, and this is the usual search for linear complexity O (n)