using the recent result by Iacono and Langermann [@LI16], we resolve an open problem in [@FOCS15], showing that Greedy costs at most $O(\log d)\cdot |X|$ on every $d$-decomposable sequence, matching the lower bound in [@FOCS15].[^8]

In another direction, we connect multiple fingers and generalized monotone sequences. In [@FOCS15], we showed that ${\mbox{\sf OPT}}(X) \leq |X|\cdot 2^{O(d^2)}$ on every $d$-monotone sequence $X$; a sequence is $d$-monotone if it can be decomposed into $d$ increasing or $d$ decreasing sequences. Using the $k$-finger technique, we show the stronger BST property ${\mbox{\sf OPT}}(X) \leq O(d \log d) \cdot |X|$.

Concerning simple and natural BST algorithms (Splay and Greedy), we give evidence that the strongest results in the literature may still be far from settling the dynamic optimality conjecture. To this end, we describe a class of sequences for which increasing the number of fingers by one can create an $\Omega(\log n)$ gap. More precisely, we show the following:

\[thm:hierarchyx\] For every integer $k$, there is a sequence $S_k$ such that ${\mbox{\sf F}}^{k-1}(S_k) = \Omega(\frac{n}{k} \log (n/k))$ but ${\mbox{\sf F}}^{k}(S_k) = O(n)$.

Theorem \[thm:hierarchyx\] shows that the multi-finger bounds form a fine-grained hierarchy. For small $k$, our online algorithm (Theorem \[thm: online simulation\]) can match 