title: The complexity of Scheme vectors
body: <p>The <a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.6">6.3.6 Vectors</a> section in the Scheme R5RS standard states the following about vectors:</p>
  
  <blockquote>
    <p>Vectors are heterogenous structures whose elements are indexed by integers. A vector typically occupies less space than a list of the same length, and the average time required to access a randomly chosen element is typically less for the vector than for the list.</p>
  </blockquote>
  
  <p>This description of vectors is a bit diffuse. </p>
  
  <p>I'd like to know what this <em>actually</em> means in terms of the <code>vector-ref</code> and <code>list-ref</code> operations and their complexity. Both procedures returns the k-th element of a vector and a list. Is the vector operation O(1) and is the list operation O(n)? How are vectors different than lists? Where can I find more information about this? </p>
  
  <p>Right now I'm using association lists as a data structure for storing key/value pairs for easy lookup. If the keys are integers it would perhaps be better to use vectors to store the values.</p>