title: What is the runtime of operations on Java's Arraylist?
body: <p>It seems like there is no official benchmarks for some of the very commonly used classes, for example <a href="http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html" rel="nofollow noreferrer">ArrayList</a>. </p>
  
  <p>I could not find the documentation on the runtime for insert or remove. Compared to Python's <a href="http://wiki.python.org/moin/TimeComplexity" rel="nofollow noreferrer">List</a>, which is similar to ArrayList, there is a well documented runtime complexity (see link above). </p>
  
  <p><a href="https://stackoverflow.com/questions/6101789/why-does-javas-arraylists-remove-function-seem-to-cost-so-little">This post</a>, gave some somewhat detailed benchmark on removing and copying elements from an ArrayList, but it still doesn't give the exact complexity analysis. I'm working on a project which takes extremely long data (~500,000 data points) so I can't sit back and assume removing or inserting data from ArrayList operates in constant time like magic. <strong>Where can I find this information?</strong></p>