title: What is the time complexity of the ArrayList.add method?
body: <p>The <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html" rel="nofollow noreferrer">java documentation</a> for <code>class ArrayList&lt;E&gt;</code> specifies that:</p>
  <blockquote>
  <p>The <code>size</code>, <code>isEmpty</code>, <code>get</code>, <code>set</code>, <code>iterator</code>, and <code>listIterator</code> operations run in constant time. The <code>add</code> operation runs in <em>amortized constant time</em>, that is, adding <strong>n</strong> elements requires <strong>O(n)</strong> time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the <code>LinkedList</code> implementation.</p>
  <p>Each <code>ArrayList</code> instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an <code>ArrayList</code>, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.</p>
  </blockquote>
  <p>How is this possible?</p>
  <p>The method <code>void add​(int index, E element)</code>    inserts the specified element at the specified position in this list, shifting all subsequent elements to the right. While it seems possible to achieve <em>amortized constant time</em> to insert <strong>n</strong> elements at the end of the <code>ArrayList</code> by reallocating the backing array using geometric growth, this would not allow for <em>amortized constant time</em> when inserting elements in the middle of the array.</p>
  <p>Does the documentation only refer to the <code>add(element E)</code> method or is there a neat trick to achieve <em>amortized constant time</em> in all cases?</p>