# Two-Way Linear Probing Revisited
## 4 Lower Bounds
### Universal Lower Bound  
The following lower bound holds for any two-way linear probing hashing scheme, in particular, the ones that are presented in this article.  
Figure 4: Algorithm \(\textsc{WalkFirst}(n,m)\) inserts each key into the terminal cell that belongs to the least crowded block, breaking ties arbitrarily.  
Figure 3: An illustration of algorithm \(\textsc{DecideFirst}(n,m)\). The hash table is divided into blocks of size \(\beta_{2}\). The number under each block is its weight. Each key decides first to land into the block of smaller weight, breaking ties randomly, then probes linearly to find its terminal cell.  
**Theorem 5**: _Let \(n\in\mathbb{N}\), and \(m=\lfloor\,\alpha n\,\rfloor\), where \(\alpha\in(0,1)\) is a constant. Let \(\mathbf{A}\) be any two-vaw linear probing algorithm that inserts \(m\) keys into a hash table of size \(n\). Then upon termination of \(\mathbf{A}\), w.h.p., the table contains a cluster of size of at least \(\log_{2}\log n-O(1)\)._  
Imagine that we have a bin associated with each cell in the hash table. Recall that, for each key \(x\), algorithm \(\mathbf{A}\) chooses two initial cells, and hence two bins, independently and uniformly at random, with replacement. Algorithm \(\mathbf{A}\), then, probes linearly to find two (possibly identical) terminal cells, and inserts the key \(x\) into one of them. Now imagine that after the insertion of each key \(x\), we also insert a ball into the bin associated with the initial cell from which the algorithm started probing to reach the terminal cell into which the key \(x\) was placed. If both of the initial cells lead to the same terminal cell, then we break the tie randomly. Clearly, if there is a bin with \(k\) balls, then there is a cluster of size of at least \(k\), because the \(k\) balls represent \(k\) distinct keys that belong to the same cluster. However, Theorem 1 asserts that the maximum bin load upon termination of algorithm \(\mathbf{A}\) is at least \(\log_{2}\log n-O(1)\), w.h.p.  
The above lower bound is valid for all algorithms that satisfy Definition 1. A more general lower bound can be established on all open addressing schemes that use two linear probe sequences where the initial hashing cells are chosen according to some (not necessarily uniform or independent) probability distributions defined on the cells. We still assume that the probe sequences are used to find two (empty) terminal hashing cells, and the key is inserted into one of them according to some strategy. We call such schemes _non-uniform two-way linear probing_. The proof of the following theorem is basically similar to Theorem 5, but by using instead [PERSON]'s lower bound as stated in Theorem 3.  
**Theorem 6**: _Let \(n\in\mathbb{N}\), and \(m=\lfloor\,\alpha n\,\rfloor\), where \(\alpha\in(0,1)\) is a constant. Let \(\mathbf{A}\) be any non-uniform two-way linear probing algorithm that inserts \(m\) keys into a hash table of size \(n\) where the initial hashing cells are chosen according to some probability distributions. Then the maximum cluster size produced by \(\mathbf{A}\), upon termination, is at least \(\log\log n/(2\log\phi_{2})-O(1)\), w.h.p._