title: Hash tables - complexity of insert, search, and delete
body: <p>I've been given two homework problems on the complexity of hash tables, but I'm struggling to understand the difference between them.</p>
  
  <p>They are as follows:</p>
  
  <p>Consider a hash function which is to take n inputs and map them to a table of size m.</p>
  
  <ol>
  <li><p>Write the complexity of insert, search, and deletion for the hash function which distributes all n inputs evenly over the buckets of the hash table.</p></li>
  <li><p>Write the complexity of insert, search, and deletion for the (supposedly perfect but unrealistic) hash function which will never has two items to the same bucket, i.e. this hash function will never result in a collision.</p></li>
  </ol>
  
  <p>These two questions seem quite similar to me and I'm not really sure of their differences.</p>
  
  <p>For question one, since the n inputs are distributed evenly we can assume there will be zero or one items in each bucket, so all of insert, search and delete will be O(1). Is this correct?</p>
  
  <p>How then does question two differ in any way? If the function never results in a collision then all the items will be spread evenly so wouldn't this result in O(1) for each operation?</p>
  
  <p>Is my thinking correct for these problems or am I missing something?</p>
  
  <p>EDIT: </p>
  
  <p>I believe I've identified where I've gone wrong. O(1) is correct for every operation in question 3 because the hash function is ideal and never results in collision.</p>
  
  <p>However for question 2, the items are spread evenly BUT DOES NOT MEAN there is only 1 item in each bucket, every bucket could have 20 items in a linked list, for example. So insertion would be O(1).</p>
  
  <p>But what about search? It would be O(1) + cost of searching the linked list. But we don't know the size, only know it's spread evenly. Can we get an expression for the length in terms of n (number of inputs) and m (size of table)?</p>