title: Question(s) about time complexity of array "resizing" in Java
body: <p><strong>NOTE:</strong> As the title already hints, this question is <strong>not</strong> about the specific <code>java.util.ArrayList</code> implementation of an array-based list, but rather about the raw arrays themselves and how they might behave in a "pure" (meaning completely unoptimized) array-based list implementation. I chose to mention <code>java.util.ArrayList</code> because it is the most prominent example of an array-based list in Java, although it is technically not "pure", as it utilizes preallocation to reduce the operation time of <code>add()</code>. If you want to know why I am asking this specific question without being interested in the <code>java.util.ArrayList()</code> preallocation optimization, I added a little explanation of my use case below.</p>
  
  <p>It is generally known that you can access elements in array-based lists (like Java's <code>ArrayList&lt;E&gt;</code>) with a time complexity of <code>O(1)</code>, while adding elements to that list will take <code>O(n)</code>. With linked lists, it is the other way round (for a doubly linked list, you could optimize the access to half the execution time).</p>
  
  <p>The reason why adding elements to an array-based list takes <code>O(n)</code> is that an array cannot simply be resized, but has to be reallocated and re-filled. The easiest way to do this would be:</p>
  
  <pre><code>String arr[] = new String[n];
  //...
  String newElem = "foo";
  String[] newArr = new String[n + 1];
  int i = 0;
  for (String elem : arr) {
      newArr[i] = arr[i++];
  }
  newArr[i] = newElem;
  arr = newArr;
  </code></pre>
  
  <p>The time complexity <code>O(n)</code> is clearly visible thanks to the for loop. But there are other ways to copy arrays in Java, for example <code>System.arraycopy()</code>.</p>
  
  <p>Sticking to the vanilla for loop solution, even <em>shrinking</em> an array will take <code>O(n)</code>, because an array has a fixed size and in order to "shrink" it, you'd have to copy all elements to be retained to a new, smaller array.</p>
  
  <p>So, here are my questions concerning such array operations and their time complexity:</p>
  
  <ol>
  <li><p>While the vanilla for loop will always take <code>O(n)</code>, is it possible that <code>System.arraycopy()</code> optimizes the "add" operation if there is enough space in the memory to expand the array in place, meaning that it would leave the original array at its place and just add the new element at the end of it?</p></li>
  <li><p>As the shrinking operation could <em>always</em> be executed with <code>O(1)</code> in theory, does <code>System.arraycopy()</code> always optimize this operation to <code>O(1)</code>?</p></li>
  <li><p>If <code>System.arraycopy()</code> is <em>not</em> capable of using those optimizations, is there any other way in Java to actually utilize those optimizations which are possible in theory <em>OR</em> will array "resizing" always take <code>O(n)</code>, no matter under which circumstances?</p></li>
  </ol>
  
  <p>TL;DR is there any situation in which the "resizing" of an array in Java will take less than <code>O(n)</code>?</p>
  
  <p>Additional information:</p>
  
  <p>I am using openJDK11 (newest release), but if the answer turns out to be JVM-dependent, I'd like to know how other JVMs would behave in comparison.</p>
  
  <h1>For the curious ones</h1>
  
  <p>who want to know what I want to do with this information:</p>
  
  <p>I am working on a new <code>java.util.List</code> implementation, namely a hybrid list that can store data in an array <em>and</em> in a linked buffer. On certain occasions, the buffer will be flushed into the array, which of course requires that the existing array is resized. But apart from this idea, I want to utilize as many other optimizations on the array part as possible. To avoid array resizing in general, I experimented with the idea of letting the array persist in a constant size, but managing the "valid" range of it with some other fields. Meaning that if you were to pop the last element of the array, it would not shrink the array but rather the range of valid elements. Then, when inserting new elements in the array part, the former invalid section can be used to shift values into, basically reusing the space that was formerly used by a now deleted element. If the inserting operations exceed the actual array size, elements can still be transferred to the linked buffer to avoid resizing. To further optimize this, I chose to use the middle of the array as a pivot when deleting certain elements. Now the valid range might not start at the beginning of the array anymore. Basically this means if you delete an element to the left of the pivot, all elements between the start of the valid range and the deleted element get shifted towards the pivot, to the right. Removing element to the right of the pivot works accordingly. So, after some removals, the array could look like this:</p>
  
  <pre><code>[null null|elem0 elem1 elem2||elem3 elem4 elem5|null null null]
  </code></pre>
  
  <p>(Where the | at the beginning and at the end mark the valid range and the || marks the pivot)</p>
  
  <p>So, how is this all related to my question?</p>
  
  <p>All of those optimizations build up upon the claim that array resizing is expensive in time, namely <code>O(n)</code>. Therefore array resizing is avoided whenever possible. Those optimizations might sound neat, but the code implementing them can get quite messy, <em>especially</em> when implementing the batch operations (<code>addAll()</code>, <code>removeAll()</code>, <code>retainAll()</code>...). So, if it turns out that the array resizing operation itself can be less expensive in some cases (especially shrinking), I would cut out a lot of those optimizations which are then rendered useless, making the code a <em>lot</em> easier in the process.</p>
  
  <p>So, before sticking to my optimization ideas and experiments, I'd like to know whether they are even needed.</p>