Interleave lower bound

Definition

The Lower Bound Statement and its Proof

Theorem —  Let ${\displaystyle X}$ be an access sequence. Denote by ${\displaystyle IB(X)}$ the interleave bound of ${\displaystyle X}$, then ${\displaystyle {\mathit {IB}}(X)/2-n}$ is a lower bound of ${\displaystyle OPT(X)}$, the cost of optimal offline BST that serves ${\displaystyle X}$.

Proof

Lemma 1 — The transition point of a node ${\displaystyle y}$ in ${\displaystyle P}$ at a time ${\displaystyle i}$ exists and it is unique.^[4]

Define ${\displaystyle \ell }$ to be the lowest common ancestor of all nodes in ${\displaystyle T_{i}}$ that are in Left(y). Given any two nodes ${\displaystyle a<b}$ in ${\displaystyle T_{i}}$, the lowest common ancestor of ${\displaystyle a}$ and ${\displaystyle b}$, denoted by ${\displaystyle lca(a,b)}$, satisfies the following inequalities. ${\displaystyle a\leq lca(a,b)\leq b}$. Consequently, ${\displaystyle \ell }$ is in Left(y), and ${\displaystyle \ell }$ is the unique node of minimum depth in ${\displaystyle T_{i}}$. Same reasoning can be applied for ${\displaystyle r}$, the lowest common ancestor of all nodes in ${\displaystyle T_{i}}$ that are in Right(y). In addition, the lowest common ancestor for all the points in Left(y) and right(y) is also in one of these sets. Therefore, the unique minimum depth node must be among the nodes of Left(y) and right(y). More precisely, it is either ${\displaystyle \ell }$ or ${\displaystyle r}$. Suppose, it is ${\displaystyle \ell }$. Then, ${\displaystyle \ell }$ is an ancestor of ${\displaystyle r}$. Consequently, ${\displaystyle r}$ is a transition points since the path from the root to ${\displaystyle r}$ contains ${\displaystyle \ell }$. Moreover, any path in ${\displaystyle T_{i}}$ from the root to a node in the sub-tree of ${\displaystyle y}$ must visit ${\displaystyle \ell }$ because it is the ancestor of all such nodes, and for any path to a node in the right region must visit ${\displaystyle r}$ because it is lowest common ancestor of all the nodes in right(y). To conclude, ${\displaystyle r}$ is the unique transition point for ${\displaystyle y}$ in ${\displaystyle T_{i}}$.

Lemma 2 — Given a node ${\displaystyle y}$. Suppose ${\displaystyle z}$ is the transition point of ${\displaystyle y}$ at a time ${\displaystyle j}$. If an access algorithm for a BST does not touch ${\displaystyle z}$ in ${\displaystyle T_{i}}$ for ${\displaystyle i\in [j,k]}$, then the transition point of ${\displaystyle y}$ will remain ${\displaystyle z}$ in ${\displaystyle T_{i}}$ for ${\displaystyle i\in [j,k]}$. ^[4]

Consider the same definition for ${\displaystyle \ell }$ and ${\displaystyle r}$ as in Lemma 1. Without loss of generality, suppose also that ${\displaystyle \ell }$ is an ancestor of ${\displaystyle r}$ in the BST at time ${\displaystyle j}$, denoted by ${\displaystyle T_{j}}$. As a result, ${\displaystyle r}$ will be the transition point of ${\displaystyle y}$. By hypothesis, the BST algorithm does not touch the transition point, in our case ${\displaystyle r}$, for the entirety of ${\displaystyle [j,k]}$. Therefore, it does not touch any node in Right(y). Consequently, ${\displaystyle r}$ remains the lowest common ancestor for any two nodes in Right(y). However, the access algorithm might touch a node in Left(y). More precisely, it might touch the lowest common ancestor of all nodes in Left(y) at a time ${\displaystyle i}$, which we will denoted by ${\displaystyle \ell _{i}}$. Even so, ${\displaystyle \ell _{i}}$ will remain the ancestor of ${\displaystyle r}$ for the following reasons: Firstly, observe that any node of Left(y) that was outside the tree rooted at ${\displaystyle r}$ at time ${\displaystyle j}$ cannot enter this tree at a time ${\displaystyle i\in [j,k]}$, since ${\displaystyle r}$ isn't touched in this time frame. Secondly, there exists at least one node ${\displaystyle \ell _{i}'}$ in Left(y) outside the tree rooted at ${\displaystyle r}$, for any time ${\displaystyle i\in [j,k]}$. This is since ${\displaystyle \ell }$ was initially outside ${\displaystyle r}$'s sub-tree, and no nodes from outside the tree can enter it in this timeframe. Now, consider ${\displaystyle a_{i}=lca(\ell _{i}',r)}$. ${\displaystyle a_{i}}$ cannot be ${\displaystyle r}$ since ${\displaystyle \ell _{i}'}$ is not in the sub-tree of ${\displaystyle r}$. So, ${\displaystyle a_{i}}$ must be in Left(y), since ${\displaystyle \ell _{i}'\leq a_{i}\leq r}$. Consequently ${\displaystyle \ell _{i}}$ must be an ancestor of ${\displaystyle a_{i}}$ and by consequence an ancestor of ${\displaystyle r}$ at time ${\displaystyle i}$. Therefore, there always exists a node in Left(y) on the path from the root to ${\displaystyle r}$, and as such ${\displaystyle r}$ remains the transition point.

Lemma 3 — Given a BST at time ${\displaystyle i}$, ${\displaystyle T_{i}}$, any node ${\displaystyle y}$ in ${\displaystyle T_{i}}$ can be only a transition for at most one node in ${\displaystyle P}$.^[4]

Given two distinct nodes ${\displaystyle y_{1},y_{2}\in P}$. Let ${\displaystyle r_{1},\ell _{1},r_{2},\ell _{2}}$ be the lowest common ancestor of ${\displaystyle Right(y_{1}),Left(y_{1}),Right(y_{2}),Left(y_{2})}$ respectively. From Lemma 1, we know that the transition point of ${\displaystyle y_{i}}$ is either ${\displaystyle \ell _{i}}$ or ${\displaystyle r_{i}}$ for ${\displaystyle i\in \{1,2\}}$. Now we have two main cases to consider.

Case 1: There is no ancestrally relation between ${\displaystyle y_{1}}$ and ${\displaystyle y_{2}}$ in ${\displaystyle P}$. Consequently, the ${\displaystyle Left(y_{1}),Left(y_{2}),Right(y_{1}),}$ and ${\displaystyle Right(y_{2})}$ are all disjoint. Thus, ${\displaystyle r_{1}\neq r_{2}\neq \ell _{1}\neq \ell _{2}}$, and the transition points are different.

Case 2: Suppose without loss of generality that ${\displaystyle y_{1}}$ is an ancestor of ${\displaystyle y_{2}}$ in ${\displaystyle P}$.

Case 2.1: Suppose that the transition point of ${\displaystyle y_{1}}$ is not in the tree rooted at ${\displaystyle y_{2}}$ in ${\displaystyle P}$. Thus, it is different from ${\displaystyle \ell _{2}}$ and ${\displaystyle r_{2}}$, and consequently the transition point of ${\displaystyle y_{2}}$.

Case 2.2: The transition point of ${\displaystyle y_{1}}$ is in the tree rooted at ${\displaystyle y_{2}}$ in ${\displaystyle P}$. More precisely, it is one of the lowest common ancestor of ${\displaystyle Left(y_{2})}$ and ${\displaystyle right(y_{2})}$. In other words, it is either ${\displaystyle \ell _{2}}$ or ${\displaystyle r_{2}}$.

Suppose ${\displaystyle a_{1}}$ is the lowest common ancestor of the sub-tree rooted at ${\displaystyle y_{1}}$ and does not contain ${\displaystyle y_{2}}$. We have ${\displaystyle \ell _{2}}$ and ${\displaystyle r_{2}}$ deeper than ${\displaystyle a_{1}}$ because one of them is the transition point. Suppose that ${\displaystyle \ell _{2}}$ is the transition point. Then, ${\displaystyle \ell _{2}}$ is less deep that ${\displaystyle r_{2}}$. In this case, ${\displaystyle \ell _{2}}$ is the transition point of ${\displaystyle y_{1}}$ and ${\displaystyle r_{2}}$ is the transition point of ${\displaystyle y_{2}}$. Similar reasoning applies if ${\displaystyle r_{2}}$ is less deep that ${\displaystyle \ell _{2}}$. In sum, the transition point of ${\displaystyle y_{1}}$ is the less deep from ${\displaystyle \ell _{2}}$ and ${\displaystyle r_{2}}$, and ${\displaystyle y_{2}}$ has the deeper one as a transition point.

In conclusion, the transition points are different in all the cases.

See also

References