title: Big-O run time for adding N items into ArrayList
body: <p>Say I'm adding N items to an <code>ArrayList</code> in Java. What is the worst-case run time for this? I know it can be O(N) to add a single item because the array may have to resize. It won't resize N times as I add N items or even a factor of N because (AFAIK) the <code>ArrayList</code> increases in capacity by some factor each time it resizes. That would mean some kind of log(N) number of resizes. So it seems like it should be O(N log(N)) to insert N items, but I'm not completely sure about this. An old computer science exam I'm looking at had the answer as O(N^2). Am I missing anything?</p>
  
  <p><code>int newCapacity = (oldCapacity * 3)/2 + 1;</code> (<a href="https://stackoverflow.com/questions/4450628/arraylist-how-does-the-size-increase">from this answer</a>)</p>