  The dynamic optimality conjecture, postulating the existence of an
$O(1)$-competitive online algorithm for binary search trees (BSTs), is among
the most fundamental open problems in dynamic data structures. Despite
extensive work and some notable progress, including, for example, the Tango
Trees (Demaine et al., FOCS 2004), that give the best currently known $O(\log
\log n)$-competitive algorithm, the conjecture remains widely open. One of the
main hurdles towards settling the conjecture is that we currently do not have
approximation algorithms achieving better than an $O(\log \log
n)$-approximation, even in the offline setting. All known non-trivial
algorithms for BST's so far rely on comparing the algorithm's cost with the
so-called Wilber's first bound (WB-1). Therefore, establishing the worst-case
relationship between this bound and the optimal solution cost appears crucial
for further progress, and it is an interesting open question in its own right.
  Our contribution is two-fold. First, we show that the gap between the WB-1
bound and the optimal solution value can be as large as $\Omega(\log \log n/
\log \log \log n)$; in fact, the gap holds even for several stronger variants
of the bound. Second, we provide a simple algorithm, that, given an integer
$D>0$, obtains an $O(D)$-approximation in time $\exp\left(O\left
(n^{1/2^{\Omega(D)}}\log n\right )\right )$. In particular, this gives a
constant-factor approximation sub-exponential time algorithm. Moreover, we
obtain a simpler and cleaner efficient $O(\log \log n)$-approximation algorithm
that can be used in an online setting. Finally, we suggest a new bound, that we
call {\em Guillotine Bound}, that is stronger than WB, while maintaining its
algorithm-friendly nature, that we hope will lead to better algorithms. All our
results use the geometric interpretation of the problem, leading to cleaner and
simpler analysis.
