however, easily be transformed into a lazy algorithm, as discussed in §\[sec2\].

Remains the issue that the optimal initial $T$ and $\vec{\ell}$ are not known. Let $B_1, \dots, B_N$ be instances of an online $k$-server algorithm (in our case Algorithm B), one for each combination of initial tree $T$ and initial server-placement $\vec{\ell}$. Note that $N = O(4^n \cdot {n^k})$. Let ${{\mathcal{M}}}$ be a “meta-algorithm” that simulates all $B_j$’s for $j=1,\dots,N$, competitive on sufficiently long input with the best $B_j$. Algorithm ${{\mathcal{M}}}$ processes $X$ in epochs of length $M = n \log n$, executing in the $i$-th epoch, for $i=1,\dots,\lceil m/M \rceil$, some $B_{\tau(i)}$ according to a (randomized) choice $\tau(i)$.

Suppose that $\vec{\ell}^*$ and $T^*$ describe the state of $B_{\tau(i)}$ chosen by ${{\mathcal{M}}}$ at the beginning of the $i$-th epoch. To switch to the state $\vec{\ell}^*$, $T^*$, ${{\mathcal{M}}}$ takes $O(n \log{n})$ elementary steps: (1) rotate the current tree to a *balanced* tree using any of the fingers ($O(n)$ steps), (2) move all fingers to their location in $\vec{\ell}^*$ ($k$ times $O(\log{n})$ steps), (3) use an arbitrary finger $f$ to rotate the tree to $T^*$ ($O(n)$ steps), (4) move $f$ back to its location in $\vec{\ell}^*$ ($O(n)$ steps). [Since $M = 