# Two-Way Linear Probing Revisited
## 5 Upper Bounds
### Two-Way Pre-Linear Probing: DecideFirst Algorithm  
The next theorem describes the worst-case performance of algorithm \(\textsc{DecideFirst}(n,m)\) with blocks of size \(\beta_{2}\) showing that the size of the largest cluster produced by the algorithm is \(\Theta(\log\log n)\), w.h.p.  
**Theorem 9**.: _Let \(n\in\mathbb{N}\), and \(m=\lfloor\,\alpha n\,\rfloor\), where \(\alpha\in(0,1)\) is a constant. There is a constant \(\eta>0\) such that, if_  
\[\beta_{2}(n):=\Bigg{\lceil}\,\frac{(1+\sqrt{2-\alpha})}{\sqrt{2-\alpha}(1- \alpha)}(\log_{2}\log n+\eta)\,\Bigg{\rceil},\]  
_then, w.h.p., the worst-case unsuccessful search time of algorithm \(\textsc{DecideFirst}(n,m)\) with blocks of size \(\beta_{2}\) is at most \(\xi_{n}:=12(1-\alpha)^{-2}(\log_{2}\log n+\eta)\), and the maximum insertion time is at most \(\xi_{n}/2\)._  
Proof.: Assume first that \(\textsc{DecideFirst}(n,m)\) is applied to a hash table with blocks of size \(\beta=\lceil\,b(\log_{2}\log n+\eta)\,\rceil\), and that \(n/\beta\) is an integer, where \(b=(1+\epsilon)/(1-\alpha)\), for some arbitrary constant \(\epsilon>0\). Consider the resulting hash table after termination ofthe algorithm. Let \(M\geq 0\) be the maximum number of consecutive blocks that are fully occupied. Without loss of generality, suppose that these blocks start at block \(i+1\), and let \(S=\{i,i+1,\ldots,i+M\}\) represent these full blocks in addition to the left adjacent block that is not fully occupied (Figure 5).  
Notice that each key chooses two cells (and hence, two possibly identical blocks) independently and uniformly at random. Moreover, any key always lands in the block of smaller weight. Since there are \(n/\beta\) blocks, and \(\lfloor\alpha n\rfloor\) keys, then by Theorem 2, there is a constant \(C>0\) such that the maximum block weight is not more than \(\lambda_{n}:=(ab+1)\log_{2}\log n+\alpha b\eta+\alpha+C\), w.h.p. Let \(A_{n}\) denote the event that the maximum block weight is at most \(\lambda_{n}\). Let \(W\) be the number of keys that have landed in \(S\), i.e., the total weight of blocks contained in \(S\). Plainly, since block \(i\) is not full, then all the keys that belong to the \(M\) full blocks have landed in \(S\). Thus, \(W\geq Mb(\log_{2}\log n+\eta)\), deterministically. Now, clearly, if we choose \(\eta=C+\alpha\), then the event \(A_{n}\) implies that \((M+1)(\alpha b+1)\geq Mb\), because otherwise, we have  
\[W\leq(M+1)(\alpha b+1)\bigg{(}\log_{2}\log n+\frac{\alpha b\eta+\alpha+C}{ \alpha b+1}\bigg{)}<Mb(\log_{2}\log n+\eta),\]  
which is a contradiction. Therefore, \(A_{n}\) yields that  
\[M\leq\frac{\alpha b+1}{(1-\alpha)b-1}\leq\frac{1+\epsilon\alpha}{\epsilon(1- \alpha)}.\]  
Recall that \((\alpha b+1)<b=(1+\epsilon)/(1-\alpha)\). Again, since block \(i\) is not full, the size of the largest cluster is not more than the total weight of the \(M+2\) blocks that cover it. Consequently, the maximum cluster size is, w.h.p., not more than  
\[(M+2)(\alpha b+1)(\log_{2}\log n+\eta)\leq\frac{\psi(\epsilon)}{(1-\alpha)^{2 }}(\log_{2}\log n+\eta),\]  
where \(\psi(\epsilon):=3-\alpha+(2-\alpha)\epsilon+1/\epsilon\). Since \(\epsilon\) is arbitrary, we choose it such that \(\psi(\epsilon)\) is minimum, i.e., \(\epsilon=1/\sqrt{2-\alpha}\); in other words, \(\psi(\epsilon)=3-\alpha+2\sqrt{2-\alpha}<6\). This concludes the proof as the maximum unsuccessful search time is at most twice the maximum cluster size plus two.  
We have showed that, w.h.p., the maximum cluster size produced by DecideFirst\((n,m)\) is in fact not more than  
\[\frac{3-\alpha+2\sqrt{2-\alpha}}{(1-\alpha)^{2}}\log_{2}\log n+O(1)<\frac{6} {(1-\alpha)^{2}}\log_{2}\log n+O(1).\]