# Two-Way Linear Probing Revisited
## 5 Upper Bounds
### Two-Way Post-Linear Probing: WalkFirst Algorithm  
Next, we analyze the worst-case performance of algorithm WalkFirst\((n,m)\) with blocks of size \(\beta_{3}\). Recall that the maximum unsuccessful search time is bounded from above by twice the maximum cluster size plus two. The following theorem asserts that upon termination of the algorithm, it is most likely that every block has at least one empty cell. This implies that the length of the largest cluster is at most \(2\beta_{3}-2\). Figure 5: A portion of the hash table showing the largest cluster, and the set \(S\), which consists of the full consecutive blocks and their left neighbor. **Theorem 10**. : _Let \(n\in\mathbb{N}\), and \(m=\lfloor\) an \(\rfloor\), for some constant \(\alpha\in(0,1/2)\). Let \(\delta\in(2\alpha,1)\) be an arbitrary constant, and define_  
\[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]  
_Upon termination of algorithm \(\textsc{WalkFirst}(n,m)\) with blocks of size \(\beta_{3}\), the probability that there is a fully loaded block goes to zero as \(n\) tends to infinity. That is, w.h.p., the maximum unsuccessful search time of \(\textsc{WalkFirst}(n,m)\) is at most \(4\beta_{3}-2\), and the maximum insertion time is at most \(4\beta_{3}-4\)._  
We define for each key \(t\) a _full history tree_\(T_{t}\) that describes essentially the history of the block that contains the \(t\)-th key up to its insertion time. It is a colored binary tree that is labeled by key numbers except possibly the leaves, where each key refers to the block that contains it. Thus, it is indeed a binary tree that represents all the pairs of blocks available for all other keys upon which the final position of the key \(t\) relies. Formally, we construct the binary tree node by node in Breadth-First-Search (bfs) order as follows. First, the root of \(T_{t}\) is labeled \(t\), and is colored white. Any white node labeled \(\tau\) has two children: a left child corresponding to the block \(X_{\tau}\), and a right child corresponding to the block \(Y_{\tau}\). The left child is labeled and colored according to the following rules:  
1. If the block \(X_{\tau}\) contains some keys at the time of insertion of key \(\tau\), and the last key inserted in that block, say \(\sigma\), has not been encountered thus far in the bfs order of the binary tree \(T_{t}\), then the node is labeled \(\sigma\) and colored white. 2. As in case (a), except that \(\sigma\) has already been encountered in the bfs order. We distinguish such nodes by coloring them black, but they are given the same label \(\sigma\). 3. If the block \(X_{\tau}\) is empty at the time of insertion of key \(\tau\), then it is a \"dead end\" node without any label and it is colored gray. Next, the right child of \(\tau\) is labeled and colored by following the same rules but with the block \(Y_{\tau}\). We continue processing nodes in bfs fashion. A black or gray node in the tree is a leaf and is not processed any further. A white node with label \(\sigma\) is processed in the same way we processed the key \(\tau\), but with its two blocks \(X_{\sigma}\) and \(Y_{\sigma}\). We continue recursively constructing the tree until all the leaves are black or gray. See Figure 6 for an example of a full history tree. Notice that the full history tree is totally deterministic as it does not contain any random value. It is also clear that the full history tree contains at least one gray leaf and every internal (white) node in the tree has two children. Furthermore, since the insertion process is sequential, node values (key numbers) along any path down from the root must be decreasing (so the binary tree has the heap property), because any non-gray child of any node represents the last key inserted in the block containing it at the insertion time of the parent. We will not use the heap property, however.