title: Array's lookup time complexity vs. how it is stored
body: <p>It's well known that the time complexity of array access by index is O(1).</p>
  
  <p>The documentation of Java's <code>ArrayList</code>, which is backed by an array, says the same about its <code>get</code> operation:</p>
  
  <blockquote>
    <p>The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.</p>
  </blockquote>
  
  <p>The lookup is done by getting the memory address of the element at a given index independently of the array's size (something like <code>start_address + element_size * index</code>). My understanding is that the array's elements have to be stored next to each other in the memory for this lookup mechanism to be possible.</p>
  
  <p>However, from <a href="https://stackoverflow.com/questions/10224888/java-are-1-d-arrays-always-contiguous-in-memory">this question</a>, I understand that arrays in Java are not guaranteed to have their elements stored contiguously in the memory. If that is the case, how could it always be O(1)?</p>
  
  <hr>
  
  <p>Edit: I'm quite aware of how an <code>ArrayList</code> works. My point is, if contiguous storage for arrays is not guaranteed by the JVM specification, its elements could be at different areas in the memory. Although that situation is highly unlikely, it would render the lookup mechanism mentioned above impossible, and the JVM would have another way to do the lookup, which shouldn't be O(1) anymore. At that point, it would be against both the common knowledge stated at the top of this question and the documentation of <code>ArrayList</code> regarding its <code>get</code> operation.</p>
  
  <p>Thanks everybody for your answers.</p>
  
  <hr>
  
  <p>Edit: In the end, I think it's a JVM-specific thing but most, if not all, JVM's stick to contiguous storage of an array's elements even when there's no guarantee, so that the lookup mechanism above can be used. It's simple, efficient and cost-effective.</p>
  
  <p>As far as I can see, it would be silly to store the elements all over the place and then have to take a different approach to doing the lookup.</p>