title: What's Up with O(1)?
body: <p>I have been noticing some very strange usage of O(1) in discussion of algorithms involving hashing and types of search, often in the context of using a dictionary type provided by the language system, or using dictionary or hash-array types used using array-index notation.</p>
  
  <p>Basically, O(1) means bounded by a constant time and (typically) fixed space.  Some pretty fundamental operations are O(1), although using intermediate languages and special VMs tends to distort ones thinking here (e.g., how does one amortize the garbage collector and other dynamic processes over what would otherwise be O(1) activities).</p>
  
  <p>But ignoring amortization of latencies, garbage-collection, and so on, I still don't understand how the leap to assumption that certain techniques that involve some kind of searching can be O(1) except under very special conditions.</p>
  
  <p>Although I have noticed this before, an example just showed up in the <a href="https://stackoverflow.com/questions/330978/proper-collection-to-use-to-obtain-items-in-o1-time-in-c-net">Pandincus question, "'Proper’ collection to use to obtain items in O(1) time in C# .NET?"</a>.</p>
  
  <p>As I remarked there, the only collection I know of that provides O(1) access as a guaranteed bound is a fixed-bound array with an integer index value.  The presumption is that the array is implemented by some mapping to random access memory that uses O(1) operations to locate the cell having that index.</p>
  
  <p>For collections that involve some sort of searching to determine the location of a matching cell for a different kind of index (or for a sparse array with integer index), life is not so easy.  In particular, if there are collisons and congestion is possible, access is not exactly O(1).  And if the collection is flexible, one must recognize and amortize the cost of expanding the underlying structure (such as a tree or a hash table) for <strike>which</strike> congestion relief (e.g., high collision incidence or tree imbalance).</p>
  
  <p>I would never have thought to speak of these flexible and dynamic structures as O(1).  Yet I see them offered up as O(1) solutions without any identification of the conditions that must be maintained to actually have O(1) access be assured (as well as have that constant be negligibly small).</p>
  
  <p>THE QUESTION: All of this preparation is really for a question.  What is the casualness around O(1) and why is it accepted so blindly?  Is it recognized that even O(1) can be undesirably large, even though near-constant?  Or is O(1) simply the appropriation of a computational-complexity notion to informal use?  I'm puzzled.</p>
  
  <p>UPDATE: The Answers and comments point out where I was casual about defining O(1) myself, and I have repaired that.  I am still looking for good answers, and some of the comment threads are rather more interesting than their answers, in a few cases.</p>