title: How to calculate maximum/minimum number of probes required to build a hash-table
body: <p>I'm currently working with Algorithms Fourth Edition by Robert Sedgewick and Kevin Wayne and I'm stuck on one of the exercises. I know that there's someone who's posted the solutions to many of the exercises from this book on GitHub, but I want to do them on my own so that I can understand and learn from them. </p>
  
  <p>I've been scanning the book for how to calculate the maximum/minimum number of probes required to build a hash-table (exercise 3.4.12), but I can't find any methods/functions/formulas which shows how to move forward when dealing with such a problem. </p>
  
  <p>The exercise:</p>
  
  <blockquote>
    <p>Suppose that the keys A through G, with the hash values given below, are inserted in some order into an initially empty table of size 7 (= m) using a linear-probing (when there's a collision ew just check the next entry in the table by incrementing index) table (with no resizing for this problem)</p>
    
    <p>key  = "A B C D E F G"</p>
    
    <p>hash = "2 0 0 4 4 4 2"</p>
    
    <p>Which of the following could not possibly result from inserting these keys?</p>
    
    <p>a)  E F G A C B D</p>
    
    <p>b)  C E B G F D A</p>
    
    <p>c)  B D F A C E G</p>
    
    <p>d)  C G B A D E F</p>
    
    <p>e)  F G B D A C E</p>
    
    <p>f)  G E C A D B F</p>
  </blockquote>
  
  <p>I found this website <a href="http://orion.lcg.ufrj.br/Dr.Dobbs/books/book2/algo02e5.htm" rel="nofollow noreferrer">http://orion.lcg.ufrj.br/Dr.Dobbs/books/book2/algo02e5.htm</a> , but I couldn't understand much of it. I got stumped on what to do when I tried to solve this, first I thought I had misunderstood the question, or that I simply couldn't find the formula on how to solve the exercise.</p>
  
  <p>How do I calculate the maximum and minimum number of probes that could be required to build a table of size m?</p>