# Experimental implementation of finite-time Carnot cycle

Ruo-Xun Zhai  Graduate School of China Academy of Engineering Physics, No. 10
Xibeiwang East Road, Haidian District, Beijing, 100193, China  Fang-Ming Cui
Graduate School of China Academy of Engineering Physics, No. 10 Xibeiwang East
Road, Haidian District, Beijing, 100193, China  Beijing Normal University,
Beijing 100875, China  Yu-Han Ma  Graduate School of China Academy of
Engineering Physics, No. 10 Xibeiwang East Road, Haidian District, Beijing,
100193, China  C. P. Sun<EMAIL_ADDRESS>Graduate School of China Academy
of Engineering Physics, No. 10 Xibeiwang East Road, Haidian District, Beijing,
100193, China  Beijing Computational Science Research Center, Beijing 100193,
China  Hui Dong<EMAIL_ADDRESS>Graduate School of China Academy of
Engineering Physics, No. 10 Xibeiwang East Road, Haidian District, Beijing,
100193, China

(August 27, 2024)

###### Abstract

The Carnot cycle is a prototype of ideal heat engine to draw mechanical energy
from the heat flux between two thermal baths with the maximum efficiency,
dubbed as the Carnot efficiency $\eta_{\mathrm{C}}$. Such efficiency can only
be reached by thermodynamical equilibrium processes with infinite time,
accompanied unavoidably with vanishing power - energy output per unit time. In
real-world applications, the quest to acquire high power leads to an open
question whether a fundamental maximum efficiency exists for finite-time heat
engines with given power. We experimentally implement a finite-time Carnot
cycle with sealed dry air as working substance and verify the existence of a
tradeoff relation between power and efficiency. Efficiency up to $(0.524\pm
0.034)\eta_{\mathrm{C}}$ is reached for the engine to generate the maximum
power, consistent with the theoretical prediction $\eta_{\mathrm{C}}/2$. Our
results shall provide a new platform for studying finite-time thermodynamics
consisting of nonequilibrium processes.

Heat engine is a major machinery to convert heat into the useful energy, such
as mechanic work or electricity. Sadi Carnot derived in 1824 an upper bound
$\eta_{\mathrm{C}}=1-T_{\mathrm{c}}/T_{\mathrm{h}}$ [1, 2] for the conversion
efficiency from heat to useful energy in the Carnot cycle with two isothermal
processes with the working substance in two thermal baths with temperatures
$T_{\mathrm{c}}$ and $T_{\mathrm{h}}$ and two adiabatic processes. In
isothermal processes, a control parameter is tuned in a quasi-static fashion -
physically much slower than the equilibrium time scale - to reach the Carnot
efficiency [2]. Faster processes typically result in more energy dissipation
with a consequently lower efficiency, yet can potentially increase the output
power [3]. Such tradeoff between power and efficiency suggests the possibility
to thermodynamically optimize the two, e.g. increasing efficiency while
retaining the power or vise versa [4, 5, 6, 7, 8, 9, 10]. One might wonder
what is the best achievable efficiency, if exists, for any output power posted
by the fundamental laws of thermodynamics [11, 12, 13].

Answering such question requires the quantitative evaluation of
irreversibility in the fundamental non-equilibrium thermodynamics [14, 15].
Theoretical models near equilibrium were explored recently to reveal a
tradeoff relation between power and efficiency [16, 12, 11, 13, 17]. More
importantly, a fundamental limit of efficiency with a leading order
$\eta_{\mathrm{C}}/2$ is predicted for the engine generating the maximum power
[7, 10, 9, 18]. Aside from the theoretical achievements, it remains with
urgency to devise finite-time heat engine cycles to experimentally test the
fundamental finite-time thermodynamical constraints [19, 20, 21]. The current
main difficulty to implement a finite-time Carnot cycle is to promptly change
the temperature of the thermal bath before and after the adiabatic processes,
whose duration is far shorter than the equilibrium time to avoid heat exchange
[20]. We develop an adiabatic-without-run scheme to implement the finite-time
Carnot cycle by separately running only two isothermal processes in the high-
and low-temperature baths. Without actual run of the two adiabatic processes,
we can change the bath temperature with the desired accuracy to evaluate the
performance of the finite-time Carnot engine. Our scheme allows all the
essential quantities for evaluating the engine’s performance to be obtained by
the directly measurable work in the two isothermal processes with the first
law of thermodynamics of energy conservation.

We present an experimental verification of the power-efficiency tradeoff
relation with the dry air as working substance in the finite-time Carnot
cycle, which is implemented by changing the gas volume
$V(t)=V_{0}+\mathcal{A}L(t)$ via moving a piston along a designed path $L(t)$.
$\mathcal{A}=\pi d^{2}/4$ is the area of the cross section of the cylindric
chamber with the diameter $d=5.00\mathrm{cm}$. We trace the pressure $p(t)$
with pressure sensors on the chamber. The maintenance of the bath temperature
($\pm 0.1\mathrm{K}$) is achieved by a designed water tank equipped with the
feedback temperature control unit.

Figure 1: The finite-time Carnot cycle under the temperature combination
($T_{\mathrm{h}},T_{\mathrm{c}}$) $=(319.2.0,308.2)\mathrm{K}$. a. The
Clapeyron pressure-volume ($p-V$) graph of the finite-time Carnot cycle. The
red and blue lines show the finite-time isothermal expansion ($A\rightarrow
B^{\prime}\rightarrow B$) with duration $\tau_{\mathrm{h}}$ and compression
($C\rightarrow C^{\prime}\rightarrow D$) with duration $\tau_{\mathrm{c}}$,
and the green lines show the adiabatic processes ($B\rightarrow C$ and
$D\rightarrow A$) without actual run. Two relaxation processes
($B^{\prime}\rightarrow B$ and $D^{\prime}\rightarrow D$) with the waiting
time $2\tau_{\mathrm{relax}}$ are added to allow the system to reach the
equilibrium with the thermal bath. The ideal Carnot cycle ($A\rightarrow
B\rightarrow C\rightarrow D$) is presented as the gray dashed lines for
reference. b-c. The gaseous volume $V_{\mathrm{h(c)}}(t)$ and the effective
temperature trace $\Delta T_{\mathrm{h(c)}}(t)$ during the finite-time
isothermal expansion and compression. The ideal gas is expanded or compressed
with the constant speed $L(t)=L_{0}+\nu t$, with
$\nu_{\mathrm{exp}}=20.00\mathrm{mm/s}$ and
$\nu_{\mathrm{com}}=20.00\mathrm{mm/s}$ . The total time for the example cycle
is $t_{\mathrm{tot}}=25.92\mathrm{s}$.

The Clapeyron pressure-volume ($p-V$) graph is shown in Fig. 1a with two
finite-time isothermal processes (red and blue curves) and two no-run
adiabatic processes (green curves). In each run, the system is immersed in the
water bath for $10$ seconds to allow the initial equilibration of the gas
system with the water bath. And the gas is expanded (red line $A\rightarrow
B^{\prime}$ in Fig. 1b) or compressed (blue line $C\rightarrow D^{\prime}$ in
Fig. 1c) in the two isothermal processes with constant speeds controlled by a
step motor with the precision $\pm 0.02\mathrm{mm}$. The pressure traces
$p(t)$ (red and blue curves) measured in the two processes deviates
significantly from the equilibrium pressure (dashed black curve) due to the
finite relaxation time $\tau_{\mathrm{relax}}=2.77\mathrm{s}$. After the
expansion and compression, additional waiting time ($2\tau_{\mathrm{relax}}$)
is added to allow the gas relaxing to the equilibrium state
($B^{\prime}\rightarrow B$ and $D^{\prime}\rightarrow D$). The four piston
positions ($A,B,C,D$) are designed (see supplementary materials) for each
temperature combination ($T_{\mathrm{h}}$,$T_{\mathrm{c}}$) to ensure the
connection between the end ($B$ and $D$) of one finite-time isothermal process
to the beginning ($C$ and $A$) of the other one with adiabatic processes. We
run the engine cycles with 10 temperature combinations to span the Carnot
efficiency from $\eta_{\mathrm{C}}=$0.0063 with the temperature combination
$(313.2,311.2)\mathrm{K}$ to $\eta_{\mathrm{C}}=0.0343$ with
$(319.2.0,308.2)\mathrm{K}$.

Figure 2: Power and efficiency of the finite-time Carnot engine under the
temperature combination ($T_{\mathrm{h}},T_{\mathrm{c}}$)
$=(319.2.0,308.2)\mathrm{K}$. a. Output power
$P(\tau_{\mathrm{h}},\tau_{\mathrm{c}})$ as a function of operation time
($\tau_{\mathrm{h}},\tau_{\mathrm{c}}$). Each blue circle shows the output
power averaged over 8 repeats of the measurement. The arrow shows the position
of the maximum power with the control time
$\tau_{\mathrm{h}}^{*}=13.32\mathrm{s}$ and
$\tau_{\mathrm{c}}^{*}=12.60\mathrm{s}$. b. Efficiency-power tradeoff (blue
circles with error bar). The dashed green curve shows the Carnot efficiency
$\eta_{\mathrm{C}}=0.0343$, and the blue shadow presents the efficiency
fluctuation due to temperature variation of the water bath during the
experiments. The dashed red line shows the theoretical constraint [13] between
the normalized efficiency $\widetilde{\eta}\equiv\eta/\eta_{\mathrm{C}}$ and
power $\widetilde{P}\equiv P/P_{\mathrm{max}}$ with the upper bound
$\widetilde{\eta}\leq
1-\left(1-\eta_{\mathrm{C}}\right)\widetilde{P}/[2\left(1+\sqrt{1-\widetilde{P}}\right)-\eta_{\mathrm{C}}\widetilde{P}]$
and the lower bound $\widetilde{\eta}\geq 1-\sqrt{1-\widetilde{P}}$ with the
temperature fluctuation represented by the red shadow.

To evaluate the performance ( power and efficiency) of the designed cycle, we
calculate the work performed in each process with the integral $W(t)=-\int
p(t)\mathcal{A}dL(t)$. The heat exchange is obtained with the conservation of
energy as $\Delta Q=-W+\Delta U$, where $\Delta U$ is the internal energy
change of the gas. The important properties of the ideal gas is that its
internal energy depends only on its temperature $T_{s}$, which is
experimentally determined by the ideal gas law via the state equation
$pV=nRT_{\mathrm{s}}$ with the amount of substance of gas in moles $n$ and the
ideal gas constant $R$. The temperature deviations from the thermal bath
$\Delta T_{\mathrm{h(c)}}(t)=T_{\mathrm{s}}(t)-T_{\mathrm{h(c)}}$ are
illustrated with solid lines (cyan and purple) in Fig. 1b and 1c. The
relaxation processes at the end of each isothermal process ensure the
unchanged internal energy $\Delta U_{A\rightarrow B}=\Delta U_{C\rightarrow
D}=0$, since the gas is nearly in equilibrium with the water bath $\Delta
T_{\mathrm{h(c)}}(t)\approx 0$. The heat absorbed from the
high(low)-temperature bath is measured directly via

$Q_{\mathrm{h(c)}}=-W_{\mathrm{h(c)}}=\int_{0}^{\tau_{\mathrm{h(c)}}}p(t)\mathcal{A}\dot{L}(t)dt,$
(1)

where $\tau_{\mathrm{h}}$ ($\tau_{\mathrm{c}}$) is the operation time for the
isothermal expansion (compression) process $A\rightarrow B^{\prime}\rightarrow
B$ ($C\rightarrow D^{\prime}\rightarrow D$). The total work extracted
$W_{\mathrm{tot}}$ of the whole cycle is measured by the difference of heat
exchanges, $W_{\mathrm{tot}}=Q_{\mathrm{h}}+Q_{\mathrm{c}}$. And the power is
calculated as the total work extracted during a cycle divided by the total
duration of the cycle,
$P(\tau_{\mathrm{h}},\tau_{\mathrm{c}})=W_{\mathrm{tot}}$/($\tau_{\mathrm{h}}+\tau_{\mathrm{c}}$).
The efficiency is given by the ratio between the extracted work
$W_{\mathrm{tot}}$ and the input heat $Q_{\mathrm{h}}$ from the high-
temperature thermal bath,
$\eta(\tau_{\mathrm{h}},\tau_{\mathrm{c}})=W_{\mathrm{tot}}/Q_{\mathrm{h}}$.
In Fig. 2a, we show how the power $P(\tau_{\mathrm{h}},\tau_{\mathrm{c}})$
changes with the two operation time $\tau_{\mathrm{h}}$ and
$\tau_{\mathrm{c}}$ for one cycle under the temperature combination
($T_{\mathrm{h}},T_{\mathrm{c}}$) $=(319.2.0,308.2)\mathrm{K}$. The
competition between the increase of work (equals to the gray area enclosed by
the $p-V$ curve) and the increase of operation time results in the maximum
power $P_{\mathrm{max}}=0.030\mathrm{J}\cdot\mathrm{s}^{-1}$ on the power
surface with the control time $\tau_{\mathrm{h}}^{*}=13.32\mathrm{s}$ and
$\tau_{\mathrm{c}}^{*}=12.60\mathrm{s}$ (red arrow in Fig. 2a).

Recently, much attentions are drawn to find the tradeoff between power and
efficiency for finite-time thermodynamic cycles, e.g., Carnot cycle [7, 20].
Within the framework of the low-dissipation model [7, 9], a power and
efficiency tradeoff relation [12, 11, 13] is predicted for finite-time Carnot
cycle. Figure 2b shows the scatter plot of the normalized efficiency
$\eta/\eta_{\mathrm{C}}$ and the normalized output power $P/P_{\mathrm{max}}$
for cycles with changing operation time $\tau_{\mathrm{h}}$ and
$\tau_{\mathrm{c}}$. The error bars of each set $P$ and $\eta$ are obtained
from 8 repeats of the experimental runs. The experimental data fall into the
region enclosed by two margins of maximum and minimum efficiencies, which are
illustrated as red dashed line with a red shadow area reflecting the
fluctuation of the bath temperature in Fig. 2b. The data illustrates not only
an upper bound for the achievable efficiency, but also a lower bound for the
worst efficiency for the current finite-time Carnot cycle. The cycle achieves
the Carnot efficiency $\eta_{\mathrm{C}}=0.0343$ with the increasing operation
time $\tau_{\mathrm{c}}$ and $\tau_{\mathrm{h}}$ at the top left corner with a
vanishing power.

The key quantity to evaluate the finite-time Carnot cycle is the efficiency at
the maximum power $\eta_{\mathrm{EMP}}$, which was suggested as a physical
efficiency limit independent of the properties of the working substance [5,
9]. We extract the efficiency at the maximum power $\eta_{\mathrm{EMP}}$ for
all the temperature combinations in our experiment, and show its dependence on
the Carnot efficiency in Fig. 3a. The obtained maximum efficiencies (markers
with error bars) follow a simple relation $\eta_{\mathrm{EMP}}=(0.524\pm
0.034)\eta_{\mathrm{C}}+\mathcal{O}(\eta_{\mathrm{C}}^{2})$, which agrees well
with the Curzon-Ahlborn efficiency[5]
$\eta_{\mathrm{CA}}=1-\sqrt{1-\eta_{\mathrm{C}}}$ and the recent proposed
bound [9, 8] $\eta_{\mathrm{C}}/(2-\eta_{\mathrm{C}})$ to the first order of
the Carnot efficiency $\eta_{\mathrm{C}}$ as
$\eta_{\mathrm{EMP}}=\eta_{\mathrm{C}}/2+\mathcal{O}(\eta_{\mathrm{C}}^{2})$.
The coefficient $1/2$ was proved as a universal value independent of the
system-specific features in the linear response regime due to the symmetry of
the Onsager relations [7, 15]. Our experimental data provides the first
demonstration of the leading order with the coefficient $1/2$.

The optimization of the cycle for maximum power is achieved by choosing the
operation time $\tau_{h}$ and $\tau_{c}$. We determine the corresponding
optimal operation time ($\tau_{\mathrm{h}}^{*},\tau_{\mathrm{c}}^{*}$)
(markers in Fig. 3b) to reach the maximum power for cycles with all
temperature combinations in the current experiment. The optimal time
($\tau_{\mathrm{h}}^{*},\tau_{\mathrm{c}}^{*}$) is verified to be in the
regime where the $1/\tau$ scaling is valid [20, 22] (discussions in the
supporting materials). With higher Carnot efficiency, less optimal operation
time is needed to achieve the maximum efficiency and in turn more
irreversibility is generated.

Figure 3: Optimized finite-time Carnot cycle with maximum power. a. Efficiency
at maximum power (markers with error bars) as a function of Carnot efficiency.
The red solid line shows the linear fit
$\eta_{\mathrm{EMP}}=a+b\eta_{\mathrm{C}}$ yielding the parameters $a=\pm
7.0\times 10^{-4}$ and $b=0.524\pm 0.034$. The dashed black line shows the
Curzon-Ahlborn efficiency $\eta_{\mathrm{CA}}=1-\sqrt{1-\eta_{\mathrm{C}}}$.
b. Optimal operation time ($\tau_{\mathrm{h}}^{*},$$\tau_{\mathrm{c}}^{*}$)
for the maximum power in the cycles with different Carnot efficiencies.

We have experimentally implemented the finite-time Carnot cycle with the dry
air as working substance. For any given output power, we have shown the
existence of the highest efficiency achieved with the designed operation time.
Our results verify the existence of a universal relation of the efficiency at
maximum power
$\eta_{\mathrm{EMP}}=\eta_{\mathrm{C}}/2+\mathcal{O}(\eta_{\mathrm{C}}^{2})$
to the first order of the Carnot efficiency. We believe that our work will
spur more experimental efforts into explore the finite-time thermodynamics.

This work is supported by the National Natural Science Foundation of China
(NSFC) (Grants No. 12088101, No. 11534002, No. 11875049, No. U1930402, No.
U1930403 and No. 12047549) and the National Basic Research Program of China
(Grant No. 2016YFA0301201).

## References

  * [1] Carnot, S.  _Reflections on the Motive Power of Heat and on Machines Fitted to Develop that Power_ (J. Wiley, 1890).
  * [2] Callen, H. B.  _Thermodynamics and an Introduction to Thermostatistics_ (John Wiley & Sons, 1985).
  * [3] Andresen, B., Salamon, P. & Berry, R. S.  Thermodynamics in finite time.  _Physics today_ 63 (1984).
  * [4] Novikov, I.  The efficiency of atomic power stations.  _J. Nucl. Energy_ 7, 125–128 (1958).
  * [5] Curzon, F. L. & Ahlborn, B.  Efficiency of a carnot engine at maximum power output.  _Am. J. Phys._ 43, 22–24 (1975).
  * [6] Andresen, B., Berry, R. S., Nitzan, A. & Salamon, P.  Thermodynamics in finite time. i. the step-carnot cycle.  _Phys. Rev. A_ 15, 2086–2093 (1977).
  * [7] Van den Broeck, C.  Introduction to thermodynamics of irreversible processes.  _Phys. Rev. Lett._ 95, 190602 (2005).
  * [8] Schmiedl, T. & Seifert, U.  Efficiency at maximum power: An analytically solvable model for stochastic heat engines.  _EPL (Europhysics Letters)_ 81, 20003 (2007).
  * [9] Esposito, M., Kawai, R., Lindenberg, K. & Van den Broeck, C.  Efficiency at maximum power of low-dissipation carnot engines.  _Phys. Rev. Lett._ 105, 150603 (2010).
  * [10] Tu, Z. C.  Efficiency at maximum power of feynman's ratchet as a heat engine.  _J. Phys. A: Math. Theor._ 41, 312003 (2008).
  * [11] Ryabov, A. & Holubec, V.  Maximum efficiency of steady-state heat engines at arbitrary power.  _Phys. Rev. E_ 93, 050101 (2016).
  * [12] Shiraishi, N., Saito, K. & Tasaki, H.  Universal trade-off relation between power and efficiency for heat engines.  _Phys. Rev. Lett._ 117, 190601 (2016).
  * [13] Ma, Y.-H., Xu, D., Dong, H. & Sun, C.-P.  Universal constraint for efficiency and power of a low-dissipation heat engine.  _Phys. Rev. E_ 98, 042112 (2018).
  * [14] Prigogine, I.  _Introduction to the Thermodynamics of Irreversible Processes_ (Wiley, 1968), 3rd edition edn.
  * [15] Seifert, U.  Stochastic thermodynamics, fluctuation theorems and molecular machines.  _Rep. Prog. Phys_ 75, 126001 (2012).
  * [16] Chen, L. & Yan, Z.  The effect of heat-transfer law on performance of a two-heat-source endoreversible cycle.  _J. Chem. Phys._ 90, 3740–3743 (1989).
  * [17] Chen, Y. H., Chen, J.-F., Fei, Z. & Quan, H. T.  A microscopic theory of curzon-ahlborn heat engine.  _arXiv_ (2021).
  * [18] Holubec, V. & Ryabov, A.  Maximum efficiency of low-dissipation heat engines at arbitrary power.  _J. Stat. Mech.: Theory E._ 2016, 073204 (2016).
  * [19] Blickle, V. & Bechinger, C.  Realization of a micrometre-sized stochastic heat engine.  _Nat. Phys._ 8, 143–146 (2011).
  * [20] Martínez, I. A. _et al._ Brownian carnot engine.  _Nat. Phys._ 12, 67–70 (2015).
  * [21] Rossnagel, J. _et al._ A single-atom heat engine.  _Science_ 352, 325–329 (2016).
  * [22] Ma, Y.-H., Zhai, R.-X., Chen, J., Sun, C. P. & Dong, H.  Experimental test of the 1/t-scaling entropy generation in finite-time thermodynamics.  _Phys. Rev. Lett._ 125, 210601 (2020).


# Structural Properties of Search Trees with 2-way Comparisons††thanks:
Research supported by NSF grant CCF-2153723.

Sunny Atalig  University of California at Riverside, USA  Marek Chrobak
University of California at Riverside, USA  Erfan Mousavian  Sharif University
of Technology, Tehran, Iran  Jiri Sgall  Charles University, Prague, Czech
Republic  Pavel Vesely  Charles University, Prague, Czech Republic

###### Abstract

Optimal 3-way comparison search trees (3wcst’s) can be computed using standard
dynamic programming in time $O(n^{3})$, and this can be further improved to
$O(n^{2})$ by taking advantage of the Monge property. In contrast, the fastest
algorithm in the literature for computing optimal 2-way comparison search
trees (2wcst’s) runs in time $O(n^{4})$. To shed light on this discrepancy, we
study structure properties of 2wcst’s. On one hand, we show some new threshold
bounds involving key weights that can be helpful in deciding which type of
comparison should be at the root of the optimal tree. On the other hand, we
also show that the standard techniques for speeding up dynamic programming
(the Monge property / quadrangle inequality) do not apply to 2wcst’s.

##  1 Introduction

We have a linearly ordered set $\mathcal{K}$ of $n$ keys. We consider _two-way
comparison search trees_ (2wcst’s), namely decision trees whose internal nodes
represent equal-to comparisons or less-than comparisons to keys. Each internal
node in a 2wcst has two children, one corresponding to the “yes" answer and
the other to the “no" answer. Each leaf represents one key from $\mathcal{K}$.

Fix some 2wcst $T$. When searching in $T$, we are given a query value $q$ that
we assume to be one of the keys111We remark that this is sometimes referred to
as the _successful-query model_. In the _general model_ , a query $q$ can be
any value, and if $q\notin\mathcal{K}$ then the search for $q$ must end in the
leaf representing the inter-key interval containing $q$. Algorithms for the
succcessful-query model typically extend naturally to the general model
without affecting the running time. , that is $q\in\mathcal{K}$. We search for
$q$ in $T$ as follows: starting at the root, $q$ is compared to the key in the
current node (an equal-to or less-than test), and the search then proceeds to
its child according to the result of the comparison. For each $q$, the search
must end up in the correct leaf, namely if $q=k$ then the search must end up
in the leaf labelled $k$.

Each key $k\in\mathcal{K}$ is assigned some weight $w_{k}\geq 0$. We define
the cost of $T$ by
$\operatorname{cost}(T)=\sum_{k\in\mathcal{K}}^{n}w_{k}\cdot\operatorname{depth}(k)$,
where the depth of a key $k$ is the distance (that is, the number of
comparisons) from the leaf of $k$ to the root. This cost can be also comptued
as follows: Let $w(v)$ be the total weight of the leaves in the subtree rooted
at a node $v$. Then the cost of $T$ is $\operatorname{cost}(T)=\sum_{v\in
T^{\prime}}w(v)$, where $T^{\prime}$ is the set of the internal (comparison)
nodes of $T$. The objective is to compute a 2wcst $T$ for the given instance
that minimizes $\operatorname{cost}(T)$.

Figure 1: An example of a binary search tree, with items $1,2,3,4,5,7,8,9$. If
the weights of these items are, respectively, $10,1,2,3,1,3,1,11$, the the
cost of the tree is $10\cdot 2+1\cdot 4+2\cdot 4+3\cdot 5+1\cdot 5+3\cdot
4+1\cdot 2+11\cdot 2=88$. Adding the weights of the internal leaves, layer by
layer, we get $32+20+12+10+3+7+4=88$.

The problem of computing optimal search trees, or computing optimal decision
trees in general, is one of classical problems in the theory of algorithms.
Initial research in this area, in 1960’s and 70’s, focussed on 3-way
comparison trees (3wcst). Optimal 3wcst’s can be computed in time $O(n^{3})$
using standard dynamic programming, and Knuth [6] and Yao [9] developed a
faster, $O(n^{2})$-time algorithm by showing that such optimal trees satisfy
what is now referred to as the quadrangle inequality or the Monge property.

The standard dynamic programming approach does not apply to 2wcst’s. After
earlier attempts in [7, 8], that were shown to be flawed [5], Anderson et al.
[1] developed an algorithm with running time $O(n^{4})$. Their algorithm was
later simplified in [4]. (See [4] also for a more extensive summary of the
literature and related results.)

Thus, in spite of apparent similarity between these two problems and past
research efforts, the running time of the best algorithm for optimal 2wcst’s
is still two orders of magnitude slower than the one for 3wcst’s. To shed
light on this discrepancy, in this paper we study structure properties of
2wcst’s. Here is a summary of our results:

  * •

An algorithm for designing optimal 2wcst’s needs to determine, in particular,
whether the root node should use the equal-to test or the less-than test. Let
$W$ be the total key weight. The intuition is that there should exist
thresholds $\lambda^{-}$ and $\lambda^{+}$ on key weights with the following
properties: (i) if the heaviest key weight exceeds $\lambda^{+}\cdot W$ then
some optimum tree starts with the equal-to test in the root, and (ii) if the
heaviest key weight is below $\lambda^{-}\cdot W$ then each optimum tree
starts with the less-than test. Anderson et al. [1] confirmed this intuition
and proved that $\lambda^{+}\in[\tfrac{3}{7},\tfrac{4}{9}]$ and
$\lambda^{-}=\tfrac{1}{4}$. This was recently refined in a companion paper [2]
that shows that $\lambda^{+}=\tfrac{3}{7}$. In Section 3 we provide additional
threshold bounds, one involving _two_ largest weights, the other involving so-
called _side weights_ , and establish some tightness results.

  * •

The dynamic programming formulation for computing optimal 2wcst’s is based on
a recurrence (see Section 2) involving $O(n^{3})$ sub-problems, resulting in
an $O(n^{4})$-time algorithm [1, 4]. For many weight sequences the number of
sub-problems that need to be considered is substantially smaller than
$O(n^{3})$, but there are also sequences for which no methods are known to
reduce the number of sub-problems to $o(n^{3})$. Such sequences involve
geometrically increasing weights, say $1,\gamma,\gamma^{2},...$. In Section 4
we give a threshold result for geometric sequences, by proving that for
$\gamma<\gamma^{-}=(\sqrt{5}-1)/2\approx 0.618$ there is an optimal tree
starting with the equal-to test in the root. (Note that $\gamma^{-}$
corresponds to the weight threshold $1-\gamma^{-}\approx 0.382$, which is
smaller than $\lambda^{+}=\tfrac{3}{7}\approx 0.429$.)

  * •

As discussed earlier, the $O(n^{2})$-time algorithm for computing optimal
3wcst’s uses a dynamic-programming speed-up technique based on the so-called
quadrangle inequality [6, 9] (which is closely related to and sometimes
referred to as the Monge property). Section 5 focuses on this technique. With
a series of counter-examples, we show that neither the quadrangle inequality
nor a number of other (possibly useful) related structural properties apply to
2wcst’s.

  * •

In Section 6 we show that faster than $O(n^{4})$ algorithms for 2wcst’s can be
achieved if, roughly, the weight sequence does not grow too fast. If the
weights are from the range $[1,R]$, for some integer $R$, then there is a
simple $O(n^{3})$-time algorithm for the case when $R$ is constant. For
arbitrary $R$, we give an algorithm with running time $O(n^{3}\log(nR))$,
which beats the running time $O(n^{4})$ on instances where the weight sequence
grows slower than geometrically.

##  2 Preliminaries

#### Notation.

Recall that $\mathcal{K}$ denotes the set of keys. We will typically use
letters $i,j,k,...$ for keys. By $w_{k}$ we denote the weight of key
$k\in\mathcal{K}$. The specific key values are not relevant — in fact one can
assume that $\mathcal{K}={\left\\{{1,2,...,n}\right\\}}$. We can then
represent a problem instances simply by its weight sequence
$w_{1},\ldots,w_{n}$. For simplicity, in most of this paper we assume that all
weights are different222The extension to arbitrary weights is actually not
trivial, but it can be done without affecting the time complexity. See [4],
for example, for the discussion of this issue..

By $W=\sum_{k\in\mathcal{K}}w_{k}$ we denote the _total weight_ of the
instance, and we say that an instance is _normalized_ if $W=1$. If $T$ is an
2wcst, then its weight $w{\left({T}\right)}$ is the total weight of the
instance it handles (i.e. the sum of all weights of its leaves). If $v$ is a
node in $T$, its weight $w{\left({v}\right)}$ is the weight of the sub-tree
rooted at $v$.

For convenience, we denote an equal-to test to key $k$ as
${\langle{=k}\rangle}$ and less-than test as ${\langle{<k}\rangle}$.
Furthermore, the “left” and “right” branches of a comparison test refer to the
“yes” and ”no” outcomes respectively. To simplify some proofs, we will
sometimes label the outcomes with relation symbols “$=$”, “”$\neq$”, “$<$”,
etc.

#### Side weights.

The concept of side-weights was defined by Anderson et al. [1], who also
proved the three lemmas that follow.

Let $v$ be a node in a 2wcst $T$. Then the _side-weight_ of $v$ is

$sw{\left({v}\right)}=\begin{cases}0,&v\text{ is a leaf},\\\ w,&v\text{ is an
equal-to test on a key of weight }w,\\\
\min{\left\\{{w{\left({T_{L}}\right)},w{\left({T_{R}}\right)}}\right\\}}&v\text{
is a less-than test with sub-trees }T_{L},T_{R}.\end{cases}$

######  Lemma 2.1.

_[1]_ Let $T$ be an optimal 2wcst. Then $sw{\left({u}\right)}\geq
sw{\left({v}\right)}$ if $u$ is a parent of $v$.

######  Lemma 2.2.

_[1]_ For $n>2$, if an optimal 2wcst for any instance of $n$ keys is rooted at
an equal-to test on $i$, then $i$ is a key of maximum-weight.

#### Dynamic programming.

We now show a dynamic programming formula for the optimal cost of 2wcst’s. In
this formulation we assume that the key weights are different. This
formulation involves $O(n^{3})$ subproblems, and the cost of each involves a
minimization over $O(n)$ smaller subproblems. As shown in [4], with
appropriate data structures this leads to an $O(n^{4})$-time algorithm, that
also applies to instances with equal weight keys and to the general model with
unsuccessful queries.

Assume that $\mathcal{K}={\left\\{{1,2,...,n}\right\\}}$. Let
$a_{1},a_{2},...,a_{n}$ be the permutation of $1,2,...,n$, such that
$w_{a_{1}}<w_{a_{2}}<...<w_{a_{n}}$. For $1\leq i\leq j\leq n$ and $1\leq
h\leq n$ we define a sub-instance

$\displaystyle I^{h}_{i,j}$ $\displaystyle=$
$\displaystyle{\left\\{{i,...,j}\right\\}}\cap{\left\\{{a_{1},...,a_{h}}\right\\}}.$

Thus $I^{h}_{i,j}$ consists of all keys among $i,i+1,...,j$ whose weight is at
most $w_{a_{h}}$. Let $w^{h}_{i,j}$ be the total weight of the keys in
$I^{h}_{i,j}$.

By $C^{h}_{i,j}$ we denote the minimum cost of the 2wcst for $I^{h}_{i,j}$.
Our goal is to compute $C^{n}_{1,n}$ – the optimal cost of the 2wcst for the
whole instance.

We now give a recurrence for $C^{h}_{i,j}$. If $|I^{h}_{i,j}|=1$ then
$C^{h}_{i,j}=0$. (This corresponds to a leaf $k$, for
$I^{h}_{i,j}={\left\\{{k}\right\\}}$.) Assume that $|I^{h}_{i,j}|\geq 2$ (in
particular, $i<j$). If $a_{h}\notin I^{h}_{i,j}$ then
$C^{h}_{i,j}=C^{h-1}_{i,j}$, because in this case $I^{h}_{i,j}=I^{h-1}_{i,j}$.
If $a_{h}\in I^{h}_{i,j}$ then compute $C^{h}_{i,j}$ as follows:

$\displaystyle C^{h}_{i,j}\;$
$\displaystyle=\;w^{h}_{i,j}+\min{\left\\{{C^{h-1}_{i,j},S^{h}_{i,j}}\right\\}},\quad\textrm{where}$
(1) $\displaystyle S^{h}_{i,j}\;$
$\displaystyle=\;\min_{l=i,...,j-1}{\left\\{{C^{h}_{i,l}+C^{h}_{l+1,j}}\right\\}}.$
(2)

The two choices in the minimum formula for $C_{i,j}^{h}$ correspond to
creating an internal node, either the equal-to test
${\langle{={a_{h}}}\rangle}$ or a less-than-test ${\langle{<{l+1}}\rangle}$.
We refer to the index (key) $l$ in the formula of $S_{i,j}^{h}$ to be a “cut”
or “cut-point”, and define
$C_{i,j}^{h}{\left({l}\right)}=C^{h}_{i,l}+C^{h}_{l+1,j}$.

##  3 Threshold Results

The following results were given in [1, 2]:

######  Theorem 3.1.

_[1]_ Let $\lambda^{-}$ be the largest value such that for all
$p\in{\left({0,\lambda^{-}}\right)}$ and all normalized instances with max
key-weight $p$, there exists no optimal 2wcst rooted at an equal-to test. Then
$\lambda^{-}=\tfrac{1}{4}$.

######  Theorem 3.2.

_[1, 2]_ Let $\lambda^{+}$ be the smallest value such that for all
$p\in{\left({\lambda^{+},1}\right)}$ and all normalized instances with max
key-weight $p$, there exists an optimal 2wcst rooted at an equal-to test. Then
$\lambda^{+}=\tfrac{3}{7}$.

######  Lemma 3.1.

_[1]_ Let $\mathcal{K}$ be an instance of keys and $\mathcal{K}_{1}$ and
$\mathcal{K}_{2}$ be two complementary sub-sequences of $\mathcal{K}$. Let
$T$, $T_{1}$, and $T_{2}$ be optimal 2wcsts for $\mathcal{K}$,
$\mathcal{K}_{1}$, $\mathcal{K}_{2}$ respectively. Then
$\operatorname{cost}{\left({T_{1}}\right)}+\operatorname{cost}{\left({T_{2}}\right)}\leq\operatorname{cost}{\left({T}\right)}$.

The last lemma is in fact quite obvious: One can think of $T$ as a redundant
search tree that handles both instances $\mathcal{K}_{1}$, $\mathcal{K}_{2}$,
and the search costs for these instances add up to the cost of $T$. Removing
redundant comparisons can only decrease cost.

###  3.1 Equal-to Test Threshold for Two Heaviest Keys

In this section we provide threshold results that depend on the two heaviest
weights, that we denote by $\alpha$ and $\beta$, with $\alpha\geq\beta$. By
the threshold bound in [2], if $\alpha\geq\tfrac{3}{7}W$ then there is an
optimal 2wcst with an equal-to test in the root. The theorem below shows that
this threshold value depends on $\beta$. In fact, $\beta\geq\tfrac{1}{3}W$
already suffices for an optimal tree with an equal-to test at the root to
exist.

######  Theorem 3.3.

Consider an instance of $n\geq 2$ keys with total weight $W$. Let $\alpha$ and
$\beta$ be the first and second heaviest weights respectively, where

$2\alpha+\beta\geq W.$ (3)

Then there exists an optimal 2wcst rooted at an equal-to test.

Recall that, by Lemma 2.2, if an optimal tree’s root is an equal-to test then
we can assume that this test is to the heaviest key.

###### Proof.

We prove the theorem by induction. The base cases $n=2,3$ are trivial, so let
$n\geq 4$ and assume that the theorem holds for fewer than $n$ keys. Let $T$
be a tree for an $n$-key instance rooted at ${\langle{<r}\rangle}$. Suppose
that $2\alpha+\beta\geq w{\left({T}\right)}$. We show that we can then convert
$T$, without increasing cost, into a tree $T^{\prime}$ with an equal-to test
in the root.

We can assume that $2<r\leq n-1$ since otherwise we can replace the less-than
test by an equal-to test. So we have at least 2 nodes on each side. Let
$k_{\alpha}$ and $k_{\beta}$ be the keys with weights $\alpha$ and $\beta$.
For simplicity, we assume in the proof that keys $k_{\alpha}$ and $k_{\beta}$
are unique. The argument easily extends to the case when they are not. For
example, in some cases when the root of a subtree containing $k_{\beta}$ but
not $k_{\alpha}$ is an equal-to test, knowing that this test must be to the
heaviest key in the subtree, we let this root be
${\langle{=k_{\beta}}\rangle}$. If this root is some other key of weight
$\beta$, use this key instead in the argument, and the subsequent weight
estimates do not change.

We now break into two cases based on the location of these keys.

#### Case 1:

$k_{\alpha}$ and $k_{\beta}$ are on the same side w.r.t. $r$. We can assume
that $k_{\alpha},k_{\beta}<r$, by symmetry. The left tree $T_{L}$ handles less
than $n$ nodes, and since $w{\left({T_{L}}\right)}\leq w{\left({T}\right)}$,
we have $2\alpha+\beta\geq w{\left({T}\right)}\geq w{\left({T_{L}}\right)}$.
We can apply our inductive assumption and replace $w{\left({T_{L}}\right)}$
with an equivalent-cost tree rooted at ${\langle{=k_{\alpha}}\rangle}$. Let
$T_{1}$ be the right sub-tree of ${\langle{=k_{\alpha}}\rangle}$ and $T_{2}$
be the right sub-tree of ${\langle{<r}\rangle}$. Note that $T_{1}$ must
contain $\beta$ and $w{\left({T_{1}}\right)}\geq\beta$. To obtain
$T^{\prime}$, modify the tree by rotating ${\langle{=k_{\alpha}}\rangle}$ to
the root, which moves leaf $k_{\alpha}$ up by $1$ and $T_{2}$ down by $1$. The
change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle=\;-\alpha+w{\left({T_{2}}\right)}$
$\displaystyle=\;-\alpha+{\left({w{\left({T}\right)}-\alpha-w{\left({T_{1}}\right)}}\right)}$
$\displaystyle\alpha+w{\left({T_{1}}\right)}+w{\left({T_{2}}\right)}=w{\left({T}\right)}$
$\displaystyle\leq\;w{\left({T}\right)}-2\alpha-\beta$ $\displaystyle\beta\leq
w{\left({T_{1}}\right)}$ $\displaystyle\leq\;0$ by (3)

#### Case 2:

$k_{\alpha}$ and $k_{\beta}$ are on opposite sides w.r.t. $r$. We can assume
that $k_{\alpha}<r\leq k_{\beta}$, by symmetry. Since $T_{L}$ doesn’t contain
$k_{\beta}$, we have $w{\left({T_{L}}\right)}\leq w{\left({T}\right)}-\beta$.
By (3), we have
$\alpha\geq\textstyle{\frac{1}{2}}{\left({w{\left({T}\right)}-\beta}\right)}\geq\textstyle{\frac{1}{2}}w{\left({T_{L}}\right)}$.
So by $\lambda^{+}<\textstyle{\frac{1}{2}}$ (see [2]), we can replace $T_{L}$
with an equivalent cost tree rooted at ${\langle{=k_{\alpha}}\rangle}$. Again
let $T_{1}$ be the right sub-tree of ${\langle{=k_{\alpha}}\rangle}$ and
$T_{2}$ be the right sub-tree of ${\langle{<r}\rangle}$. We now break into two
sub-cases based on the root of $T_{2}$.

#### Case 2.1:

$T_{2}$ is rooted at an equal-to test. If $T_{2}$ is rooted at an equal-to
test and $k_{\alpha}$ is not in $T_{2}$, then this test is to key $k_{\beta}$.
Let $T_{3}$ be the right sub-tree of ${\langle{=k_{\beta}}\rangle}$. Then
consider the tree $T^{\prime}$ rooted at ${\langle{=k_{\alpha}}\rangle}$,
followed by ${\langle{=k_{\beta}}\rangle}$, then followed by
${\langle{<r}\rangle}$. In $T^{\prime}$, subtrees $T_{1}$ and $T_{3}$ go down
by $1$ and leaf $k_{\alpha}$ goes up by $1$. The change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle=\;-\alpha+w{\left({T_{1}}\right)}+w{\left({T_{3}}\right)}$
$\displaystyle=\;-\alpha+{\left({w{\left({T}\right)}-\alpha-\beta}\right)}$
$\displaystyle\alpha+\beta+w{\left({T_{1}}\right)}+w{\left({T_{3}}\right)}=w{\left({T}\right)}$
$\displaystyle=\;w{\left({T}\right)}-2\alpha-\beta$ $\displaystyle\leq\;0$

#### Case 2.2:

$T_{2}$ is rooted at an less-than test. Let $T_{2}$ be rooted at
${\langle{<i}\rangle}$, with $T_{3}$ and $T_{4}$ being the left and right
branches respectively. We may assume $w(T_{4})<\beta$, as otherwise we can do
an identical rotation as in Case 3.1. This implies that $T_{3}$ must contain
$k_{\beta}$ and $w{\left({T_{3}}\right)}\geq\beta$. We can assume that $T_{3}$
is not a leaf, for otherwise we can replace ${\langle{<i}\rangle}$ by an
equal-to test, reducing it to Case 3.1. We now break into two more sub-cases
based on the root of $T_{3}$.

#### Case 2.2.1:

$T_{3}$ is rooted at an equal-to test. Let $T_{3}$ be rooted at an equal-to
test. Since $T_{3}$ contains $k_{\beta}$ but not $k_{\alpha}$, $T_{3}$ is
rooted at ${\langle{=k_{\beta}}\rangle}$. But then, by Lemma 2.1, we have that
$w(T_{4})\geq\beta$, contradicting $w(T_{4})<\beta$. So this case is in fact
not possible.

#### Case 2.2.2:

$T_{3}$ is rooted at an less-than test. Let $T_{3}$ be rooted at
${\langle{<j}\rangle}$ with sub-trees $T_{5}$ and $T_{6}$. Then consider the
tree $T^{\prime}$ rooted at ${\langle{=k_{\alpha}}\rangle}$, followed by
${\langle{<j}\rangle}$, with ${\langle{<r}\rangle}$ and ${\langle{<i}\rangle}$
on the left and right branches respectively. Leaf $k_{\alpha}$ goes up by $1$
and $T_{1}$ and $T_{4}$ go down by 1. The change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle=\;-\alpha+w{\left({T_{1}}\right)}+w{\left({T_{4}}\right)}$
$\displaystyle=\;-\alpha+{\left({w{\left({T}\right)}-\alpha-w{\left({T_{5}}\right)}-w{\left({T_{6}}\right)}}\right)}$
$\displaystyle\leq\;w{\left({T}\right)}-2\alpha-\beta$ $\displaystyle
k_{\beta}\text{ is in }T_{5}\text{ or }T_{6}$ $\displaystyle\leq\;0$

###  3.2 Threshold for Side-Weights

With small modification, the proof for $\lambda^{-}\geq\tfrac{1}{4}$ given by
[1] can be extended to establish more general properties about side-weights,
given in Theorem 3.4 below. Corollary 3.2 that follows and the previous
thresholds are discussed in Section 3.3, and algorithmic implications of
Corollary 3.3 are discussed in Section 5.6.

Here, we borrow the convention of _side branches_ from [1], corresponding to
the side weight of a comparison node $v$. If $v$ is an equal-to test on key
$k$, then its side branch is the leaf $k$. If $v$ is a less-than test, then
its side branch is the sub-tree of least weight (break ties in weight
arbitrarily). We then refer to the other branch of $v$ as the _main branch_.

######  Theorem 3.4.

Let $T$ be an optimal tree for an instance of $n\geq 3$ keys, where $v_{0}$ is
the root of $T$ and $v_{1}$ is the root of the main branch of $v_{0}$. Then

$sw{\left({v_{0}}\right)}+sw{\left({v_{1}}\right)}\geq\tfrac{1}{2}w{\left({T}\right)}.$
(4)

###### Proof.

The proof is identical to the one for $\lambda^{-}\geq\frac{1}{4}$ given by
[1], with minor modifications. Let $T$ be an optimal tree for some instance of
$n\geq 3$ keys, and let ${\left({v_{0},v_{1},\ldots,v_{\ell}}\right)}$ be the
unique path along main branches from the root $v_{0}$ to a leaf $v_{\ell}$.
Assume for contradiction that the theorem is false, that is

$sw{\left({v_{0}}\right)}+sw{\left({v_{1}}\right)}<\textstyle{\frac{1}{2}}w{\left({T}\right)}$
(5)

Any given key is either $v_{\ell}$ or occupies a unique side branch
corresponding to some node $v_{i}$. Therefore we can express the weight of $T$
in terms of the side weights along of this path

$w{\left({T}\right)}={\left({sw{\left({v_{0}}\right)}+sw{\left({v_{1}}\right)}+\cdots+sw{\left({v_{\ell-1}}\right)}}\right)}+w{\left({v_{\ell}}\right)}.$

Note that while $v_{\ell}$ is not a side branch, the node $v_{\ell-1}$ can be
replaced with ${\langle{=v_{\ell}}\rangle}$, allowing us to treat it as a side
branch. By Lemma 2.1, we have
$w{\left({v_{\ell}}\right)},sw{\left({v_{\ell-1}}\right)}\leq
sw{\left({v_{\ell-2}}\right)}\leq\cdots\leq sw{\left({v_{2}}\right)}\leq
sw{\left({v_{1}}\right)}$. We thus get the inequality

$w{\left({T}\right)}\leq sw{\left({v_{0}}\right)}+\ell\cdot
sw{\left({v_{1}}\right)}.$

If $\ell\leq 3$, we have $w{\left({T}\right)}\leq
sw{\left({v_{0}}\right)}+sw{\left({v_{1}}\right)}+2sw{\left({v_{1}}\right)}<w{\left({T}\right)}$,
from (5), a contradiction.

So assume $\ell\geq 4$. We’ll now consider the first four nodes in the main
branch, letting $T_{i}$ be the side branch of $v_{i}$ for $0\leq i\leq 3$,
$T_{4}$ be the main branch of $v_{3}$, and $k_{i}$ be the node tested by
$v_{i}$. By Lemma 2.1 we have $w{\left({T_{0}}\right)}\geq
w{\left({T_{1}}\right)}\geq w{\left({T_{2}}\right)}\geq
w{\left({T_{3}}\right)}$, and
$w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}<\textstyle{\frac{1}{2}}w{\left({T}\right)}$
by our assumption for contradiction. Also note that if $v_{i}$ is a less-than
test, then $k_{j}$ for $j>i$ either all precede or all succeed $k_{i}$,
depending on whether $v_{i}$’s main branch is the yes or no outcome.

We’ll now modify $T$ to get a new tree $T^{\prime}$ of strictly lower cost.
First re-label the keys
${\left\\{{k_{0},k_{1},k_{2},k_{3}}\right\\}}={\left\\{{b_{0},b_{1},b_{2},b_{3}}\right\\}}$
so that $b_{i}\leq b_{j}$ for $i<j$. Like in the proofs for bounding
$\lambda^{-}$ and $\lambda^{+}$, we use one of the“inner cut-points” $b_{1}$
or $b_{2}$ to split $T$ into a wider tree. We break into two cases:

#### Case 1:

$b_{1}$ and $b_{2}$ both correspond to equal-to tests. In this case, let
$T^{\prime}$ be rooted at ${\langle{<b_{2}}\rangle}$, where the tests from $T$
on $b_{0}$ and $b_{1}$ are done on the left branch and likewise for $b_{2}$
and $b_{3}$ on the right branch. Do these tests in the same order as in the
original tree. Because we’ve introduced a new test into the tree, one $T_{i}$
must fracture, and we can show that that sub-tree must be $T_{3}$ or $T_{4}$.
In this case the sub-trees corresponding to $b_{1}$ and $b_{2}$ are leaves and
can’t split, so the sub-tree must correspond to an less-than test on $b_{0}$
or $b_{3}$, the least or greatest key. If the fractured tree $T_{i}$
corresponds to $b_{0}$ and $b_{0}=v_{i}$ for $i<3$, then this implies that the
main branch of $v_{i}$ corresponds the yes or ${\langle{\geq}\rangle}$ outcome
and $T_{i}$ is the opposite outcome. Then $T_{i}$ does not contain any other
keys $v_{j}$ for $j\neq i$ and can’t be split by ${\langle{<b_{2}}\rangle}$.
The case is symmetric if $T_{i}$ corresponds to the test on $b_{3}$.

So only $T_{3}$ or $T_{4}$ split, which does not increase cost by Lemma 3.1
(or if both are leaves, then we can remove test $v_{3}$ or $v_{4}$ from
$T^{\prime}$, only decreasing cost). By doing tests in order of the original
tree, $T_{3}$ and $T_{4}$ (or their fractured components) must be at the
bottom of $T^{\prime}$, moving up by 1 to depth 3, and $v_{0}$ will be right
below ${\langle{<b_{2}}\rangle}$, pushing down $T_{0}$ by 1 to depth 2.
Depending on which what branches they reside, $T_{1}$ and $T_{2}$ don’t change
in depth, or $T_{1}$ goes down by 1 and $T_{2}$ goes up by 1 (the latter being
the worse case since $w{\left({T_{1}}\right)}\geq w{\left({T_{2}}\right)}$).
Summarizing, our change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle\leq\;w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-w{\left({T_{2}}\right)}-w{\left({T_{3}}\right)}-w{\left({T_{4}}\right)}$
$\displaystyle=\;w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-{\left({w{\left({T}\right)}-w{\left({T_{0}}\right)}-w{\left({T_{1}}\right)}}\right)}$
$\displaystyle
w{\left({T_{0}}\right)}+...+w{\left({T_{4}}\right)}=w{\left({T}\right)}$
$\displaystyle=\;2{\left({w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}}\right)}-w{\left({T}\right)}$
$\displaystyle<\;0$ $\displaystyle
w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}<\textstyle{\frac{1}{2}}w{\left({T}\right)}$

#### Case 2:

Either $b_{1}$ or $b_{2}$ correspond to a less-than test. If $b_{1}$ or
$b_{2}$ correspond to a less-than-test, let $T^{\prime}$ be rooted at (either)
said test, then place the remaining tests from the original trees into the
appropriate branch, performing them in the same order as in $T$. We may assume
wlog that we choose $b_{1}$. Since we are not introducing a new tests, no
fracture can occur in this case. We break into cases depending on which test
$v_{i}$ (which we assume is a less-than test) is rooted at $T^{\prime}$.

Because all other $v_{i}$ lie on the same branch below $v_{0}$, $k_{0}$ is
either the least or greatest key. So $k_{0}$ can not be $b_{1}$, (unless
$b_{1}$ corresponds to an equal-to test on $k_{0}$, but we assume $b_{1}$
corresponds to a less-than-test). So $v_{0}$ can’t be the root of $T^{\prime}$

If $v_{1}$ is the root of $T^{\prime}$, then $v_{0}$ is right below $v_{1}$,
moving $T_{0}$ down by 1 at depth 2. $v_{0}$ will be in whatever outcome
corresponds to the side branch of $v_{1}$ in the original tree, which implies
that the main branch of $v_{0}$ in the new tree is $T_{1}$, staying at the
same depth 2. That means that $v_{2}$ and $v_{3}$ are on the same branch of
$v_{1}$, implying $T_{2}$, $T_{3}$, and $T_{4}$ all go up by 1. This gives a
change in cost of
$\Delta=w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-w{\left({T_{2}}\right)}-w{\left({T_{3}}\right)}-w{\left({T_{4}}\right)}<0$.

If $v_{2}$ is the root of $T^{\prime}$, then $T_{2}$ and $v_{3}$ will be on
opposite branches. If $v_{1}$ and $v_{3}$ are on the same branch of the root,
then $v_{0}$ is alone on one side, with $T_{2}$ being it’s main branch.
$T_{0}$ goes down by 1, $T_{1}$ doesn’t move, and $T_{2}$, $T_{3}$, and
$T_{4}$ go go up by 1, giving
$\Delta=w{\left({T_{0}}\right)}-w{\left({T_{2}}\right)}-w{\left({T_{3}}\right)}-w{\left({T_{4}}\right)}<0$.
If $v_{1}$ and $v_{3}$ are on opposite sides, then $v_{3}$ is alone and
$T_{2}$ is below $v_{1}$. $T_{0}$ and $T_{1}$ goes down by 1, $T_{2}$ doesn’t
move, and $T_{3}$ and $T_{4}$ both go up by 2. The change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle=\;w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-2{\left({w{\left({T_{3}}\right)}+w{\left({T_{4}}\right)}}\right)}$
$\displaystyle=\;w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-2{\left({w{\left({T}\right)}-w{\left({T_{0}}\right)}-w{\left({T_{1}}\right)}-w{\left({T_{2}}\right)}}\right)}$
$\displaystyle=\;3w{\left({T_{0}}\right)}+3w{\left({T_{1}}\right)}+2w{\left({T_{2}}\right)}-2w{\left({T}\right)}$
$\displaystyle\leq\;4w{\left({T_{0}}\right)}+4w{\left({T_{1}}\right)}-2w{\left({T}\right)}$
$\displaystyle w{\left({T_{2}}\right)}\leq w{\left({T_{1}}\right)}\leq
w{\left({T_{0}}\right)}$ $\displaystyle<\;0$ $\displaystyle
w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}<\textstyle{\frac{1}{2}}w{\left({T}\right)}$

If $v_{3}$ is the root of $T_{3}$, then $v_{0}$ is below $v_{3}$, moving
$T_{0}$ down by 1. Either $T_{1}$ and $T_{2}$ stay at the same depth, or
$T_{1}$ goes down by 1 and $T_{2}$ goes up by 1. $T_{3}$ and $T_{4}$ goes up
by at least 1. This gives a change in cost $\Delta\leq
w{\left({T_{0}}\right)}+w{\left({T_{1}}\right)}-w{\left({T_{2}}\right)}-w{\left({T_{3}}\right)}-w{\left({T_{4}}\right)}<0$.
∎

######  Corollary 3.2.

Consider an instance of $n\geq 2$ keys with total weight $W$. Let $\alpha$ and
$\beta$ be the first and second heaviest weights respectively, where

$\alpha+\beta<\tfrac{1}{2}W.$

Then there exists no optimal tree that’s rooted at two consecutive equal-to
tests.

###### Proof.

If any tree is rooted at two consecutive equal-to tests with the above
conditions, then by Lemma 2.2, $sw{\left({v_{0}}\right)}=\alpha$ and
$sw{\left({v_{1}}\right)}=\beta$, which contradicts (4). ∎

######  Corollary 3.3.

For any optimal tree $T$ rooted at $v_{0}$ for some instance of keys,
$sw{\left({v_{0}}\right)}\geq\tfrac{1}{4}w{\left({T}\right)}$.

###### Proof.

This follows immediately from Lemma 2.1 and Theorem 3.4. ∎

###  3.3 Tightness of Thresholds

As before, let $\alpha$ and $\beta$ be the heaviest weights, with
$\alpha\geq\beta$. We now consider the regions in the $(\alpha,\beta)$-plane
corresponding to guaranteed equal-to tests, no equal-to tests, or to no two-
consecutive equal-to tests. Some crucial properties have already been
established in [2] and 3.3. These bounds, together with the observations given
below determine the regions illustrated in Figure 2. Notably, in this figure,
all known bounds are straight lines, some of which form non-convex polygons.

Figure 2: Plot of the thresholds on the first and second heaviest keys
$\alpha$ and $\beta$, where the total weight is $1$. The red region
corresponds to no equal-to test, orange correponds to no two-consecutive
equal-to tests, and green corresponds to guaranteed equal-to test. The bright
red lines indicate tight borders.

Note that in addition to the bound given by Corollary 3.2, we can trivially
use $\lambda^{-}=\tfrac{1}{4}$ to establish another bound. We prove that this
one is tight.

######  Observation 3.4.

Consider an instance of $n\geq 2$ keys with total weight $W$. Let $\alpha$ and
$\beta$ be the first and second heaviest weights respectively, where
$\alpha+4\beta<W$. Then there exists no optimal tree rooted at two consecutive
equal-to tests.

Note that inequality $\alpha+4\beta<W$ implies that we in fact have $n\geq 5$.

###### Proof.

If an optimal tree’s root is an equal-to test, then it is on the
$\alpha$-weight key, with the right branch having weight $W-\alpha$ and
heaviest key having weight $\beta$. By the lemma’s assumption,
$\beta<\tfrac{1}{4}{\left({W-\alpha}\right)}$ and thus the next comparison can
not be an equal-to test, by Theorem 3.1. ∎

######  Observation 3.5.

The bound given by Theorem 3.3 is tight for $\alpha<\tfrac{2}{5}$.

###### Proof.

Let $\beta\leq\alpha$, $2\alpha+\beta=1$, and $\epsilon>0$. Consider the
instance with four keys and weights given in the table below:

1 |  2 |  3 |  4
---|---|---|---
$\textstyle{\frac{1}{2}}\alpha$ |  $\alpha$ |  $\beta-\epsilon$ |  $\textstyle{\frac{1}{2}}\alpha+\epsilon$

Note that for $\alpha<\tfrac{2}{5}$ we have
$\textstyle{\frac{1}{2}}\alpha<\beta$, so if $\epsilon$ is sufficiently small
then $\alpha$ and $\beta-\epsilon$ are the two heaviest weights. The best tree
starting with an equal-to test is uniquely given by performing
${\langle{=2}\rangle}$ then ${\langle{=3}\rangle}$ with cost
$C^{=}=4\alpha+2\beta+\epsilon$, while the best tree starting with a less-than
test is given by performing ${\langle{<3}\rangle}$ with cost
$C^{<}=4\alpha+2\beta$. Then $C^{<}<C^{=}$ and the two heaviest weights
satisfy $2\alpha+(\beta-\epsilon)<1$. (In Figure 2 this corresponds to the
vector ${\left({0,-\epsilon}\right)}$ pointing down from the line
$2\alpha+\beta=1$.) This holds for $\epsilon$ arbitrarily small. ∎

######  Observation 3.6.

The bound given by Observation 3.4 is tight for $\alpha\geq\tfrac{1}{3}$.

###### Proof.

Let $\beta\leq\alpha$, $\alpha+4\beta=1$, and $\alpha\geq\tfrac{1}{3}$.
Consider the instance with eight keys whose weights are given in the table
below

1 |  2 |  3 |  4 |  5 |  6 |  7 |  8
---|---|---|---|---|---|---|---
$\alpha$ |  $0$ |  $\beta$ |  $0$ |  $\beta$ |  $\beta$ |  $0$ |  $\beta$

Note that $\alpha\geq\tfrac{1}{3}$ implies $\beta\leq\tfrac{1}{6}$. By case
analysis, one can show that the optimal cost starting at an equal-to test is
$C^{=}=\alpha+14\beta$, which can be achieved by doing only equal-to tests.
(Alternatively, start with ${\langle{=1}\rangle}$, then do
${\langle{<5}\rangle}$, followed by equal-to tests.) Likewise, the optimal
cost starting at a less-than test is $C^{<}=2\alpha+12\beta$, which can be
achieved using ${\langle{<4}\rangle}$ or ${\langle{<5}\rangle}$ or
${\langle{<6}\rangle}$ as the root, followed by only equal-to tests in each
branch of the root. We have $C^{=}-C^{<}=2\beta-\alpha$, and by
$\alpha\geq\tfrac{1}{3}$ and $\beta\leq\tfrac{1}{6}$ we have $C^{=}\leq
C^{<}$. ∎

##  4 Structure Results for Geometric Sequences

As we show later in Section 5, it appears that the most difficult instances
are ones whose weights form a geometric sequence. For that reason,
understanding the properties of such instances and finding a special way of
handling them may yield an algorithm that beats $O{\left({n^{4}}\right)}$.

Think of the dynamic programming algorithm as a memoized recursive algorithm.
What instances will be generated? Rescale the weights so that the heaviest
weight is $1$. If the weights decrease faster than $(1-\lambda^{+})^{i}$ (that
is $\gamma<1-\lambda^{+}$) then, by the bound in [2], the optimum choice at
each step is an equal-to test, because after removing the heaviest key, the
weight of the new heaviest key is more than $\lambda^{+}$ times the new total.
That gives a trivial algorithm with complexity $O(n\log n)$.

On the other hand, suppose that the weights decrease slower than
$\large(\tfrac{3}{4}\large)^{i}$. (That is,
$\gamma>\tfrac{3}{4}=1-\lambda^{-}$.) Then the situation is not quite
symmetric. At the first step we know for certain we will make a less-than
test, but since the weights will get partitioned between the two intervals,
the maximum key weights in these intervals could be large compared to their
total weights, so for these sub-instances equal-to tests may be optimal.

Assume now that the weights of an instance form the (infinite) geometric
sequence $(\gamma^{i})_{i\geq 0}$. Then the total weight of the instance is
$1/(1-\gamma)$ and the heaviest weight $1$ is a $1-\gamma$ fraction of the
total. Define $\gamma^{-}$ be the largest value such that for all
$\gamma\in(0,\gamma^{-})$ and for each geometric instance with ratio $\gamma$
there is an optimal tree starting with the equal-to test. By the bound on
$\lambda^{+}$ in [2], we know that $\gamma^{-}\geq 1-\lambda^{+}$ =
$\frac{4}{7}$. Below we give a tight bound.

######  Theorem 4.1.

$\gamma^{-}=\phi={\left({\sqrt{5}-1}\right)}/2\approx 0.618$.

###### Proof.

$(\leq)$ To show that $\gamma^{-}\leq\phi$, consider the gemeotric instance
with weights $(\gamma^{i})_{i}$, and with the corresponding keys ordered from
left to right in decreasing order of weight. Let $C^{=}$ and $C^{<}$ be the
optimal costs of trees starting with the equal-to test and less-than test,
respectively. If starting with the equal-to test is optimal for ratio
$\gamma$, then the optimal tree will have only equal-to tests, and its cost is

$C^{=}\;=\;\sum_{i}(i+1)\gamma^{i}\;=\;\frac{1}{(1-\gamma)^{2}}$

The tree for $C^{<}$ that splits the instance between $\gamma$ and
$\gamma^{2}$ will apply the same split recursively, so computing its cost we
get

$C^{<}\;\leq\;\sum_{i}(i+2)(\gamma^{2i}+\gamma^{2i+1})\;=\;(\gamma+1)\sum_{i}(i+2)\gamma^{2i}\;=\;\frac{1}{(1-\gamma)^{2}}\cdot\frac{2-\gamma^{2}}{1+\gamma}$

Equating these values, gives $2-\gamma^{2}=1+\gamma$, so
$\gamma=\phi=0.681...$. If $\gamma>\phi$ then $2-\gamma^{2}<1+\gamma$, in
which case $C^{<}<C^{=}$. So for $\gamma>\phi$, this instance does not have an
optimal tree starting with the equal-to test.

$(\geq)$ We now show that $\gamma^{-}\geq\phi$. Consider an arbitrary
geometric instance with ratio $\gamma$, for some $\gamma<\phi$. We will show
that any such instance has a search tree that uses only equal-to tests. We
will in fact show something stronger, proving that this property holds even if
we allow more general instances and queries:

  * •

The key weights in the instance can be any subset of the geometric sequence
$(\gamma^{i})_{i}$ (not necessarily the whole sequence).

  * •

The tree can use any pre-specified set of arbitrary queries, as long as it
includes the equals-to tests to all keys. We refer to queries in this set as
_allowed_. Each allowed query can be represeted as ${\langle{\in X}\rangle}$,
where $X$ is the set of keys that satisfies this query. The equal-to test
${\langle{=k}\rangle}$ is a special case when $X={\left\\{{k}\right\\}}$.

For convenience, we identify keys by their weights, so, for example,
${\langle{=1}\rangle}$ refers to an equal-to test on the key of weight $1$.

It is now sufficient to prove the following claim: Let $T$ be a search tree
using allowed queries for an instance of $n$ keys whose weights are a subset
of the sequence $(\gamma^{i})_{i}$. Then $T$ can be converted, without
increasing cost, into a search tree $T^{\prime}$ that uses only equals-to
tests and its root is an equals-to test to the heaviest key.

The claim is trivial for $n=1,2,3$. So assume that $n\geq 4$ and that the
claim holds for trees for instances that have fewer than $n$ keys. Consider an
instance with $n$ keys. Without loss of generality, we can assume that $1$ is
in this instance. Let $T$ be a tree for this instance, and let $L$ and $R$ be
its left (yes) and right (no) subtrees. By induction, $L$ and $R$ have only
equals-to tests, with their heaviest key at their respective roots.

If $L$ or $R$ is a leaf, then we can assume that the root of $T$ is an equals-
to test. If this test is ${\langle{=1}\rangle}$, then we are done, that is
$T^{\prime}=T$. Else, this test is ${\langle{=\gamma^{a}}\rangle}$ for some
$a\geq 1$, and $R$’s root is ${\langle{=1}\rangle}$. We can then obtain
$T^{\prime}$ by swapping these two equals-to nodes.

$\boldsymbol{\Longrightarrow}$

(a) If $R$ doesn’t contain $\gamma$.

$\boldsymbol{\Longrightarrow}$

(b) If $R$ contains $\gamma$.

Figure 3: Illustration of the lower bound for $\gamma^{-}$.

So from now on we can assume that each of $L$ and $R$ has at least two leaves.
The root of $T$ is a query ${\langle{\in L}\rangle}$. (Slightly abusing
notation, we use $L$ both for a subtree and its set of keys.) We can assume
that $1$ is in $L$, for otherwise in the rest of the proof we can swap the
roles of $L$ and $R$. Then, by the inductive assumption, the root of $L$ is
${\langle{=1}\rangle}$. Let $L^{\prime}$ be the no-subtree of the node
${\langle{=1}\rangle}$. If $R$ does not contain $\gamma$ then its total weight
is at most $\gamma^{2}/(1-\gamma)<\phi^{2}/(1-\phi)=1$, in which case we can
rotate ${\langle{=1}\rangle}$ upwards, obtaining tree $T^{\prime}$ with
smaller cost (see Figure 3(a)).

If $R$ contains $\gamma$ then, by the inductive assumption, its root is
${\langle{=\gamma}\rangle}$. Let $R^{\prime}$ be the no-subtree of
${\langle{=\gamma}\rangle}$. Then the largest key weight in $L^{\prime}\cup
R^{\prime}$ is at most $\gamma^{2}$, so the total weight of $L^{\prime}\cup
R^{\prime}$ is less than $1$ (as in the argument above). Then we can rotate
upwards both tests ${\langle{=1}\rangle}$ and ${\langle{=\gamma}\rangle}$, as
in Figure 3(b), obtaining our new tree $T^{\prime}$ with smaller cost. ∎

We can similarly define the other threshold for geometric sequences: Let
$\gamma^{+}$ be the smallest value such that for all $\gamma\in(\gamma^{+},1)$
and each geometric instance with ratio $\gamma$ the optimal tree for this
instance does not have the equal-to test at the root. By the bound on
$\lambda^{-}$, we know that $\gamma^{+}\leq 1-\lambda^{-}=\tfrac{3}{4}$. Some
improvements to this bound are probably not difficult, but establishing a
tight bound seems more challenging.

##  5 Attempts at Dynamic Programming Speedup

In the dynamic programming formulations of some optiomization problems, the
optimum cost function satisfies the so-called _quadrangle inequality_. In its
different incarnations this property is sometimes referred to as the _Monge
property_ and is also closely related to the _total monotonicity of matrices_
(see [3]). The quadrangle inequality was used, in particular, to obtain
$O(n^{2})$-time algorithms for computing optimal 3-way comparison search trees
[6, 9].

Recall that in our dynamic programming formulation (Section 2) by
$C^{h}_{i,j}$ we denote the minimum cost of the 2wcst for $I^{h}_{i,j}$, which
is the sub-problem that includes the keys in the interval $[i,j]$ which are
also among the $h$ lightest keys. In this context, the quadrangle inequality
would say that for all $i\leq i^{\prime}\leq j\leq j^{\prime}$ we have

$\displaystyle C^{h}_{i,j}+C^{h}_{i^{\prime},j^{\prime}}$ $\displaystyle\leq$
$\displaystyle C^{h}_{i,j^{\prime}}+C^{h}_{i^{\prime},j}.$ (6)

The consequence of the quadrangle inequality is that the minimizers along the
diagonals of the dynamic programming matrix satisfy a certain monotonicity
property. Namely, for any $i,j,h$, let $L^{h}_{i,j}$ be the minimizer for
$S^{h}_{i,j}$, defined as the index $l$ such that
$S^{h}_{i,j}=C^{h}_{i,l}+C^{h}_{l+1,j}$. Then the quadrangle inequality
implies that

$\displaystyle L^{h}_{i,j-1}\;\leq\;L^{h}_{i,j}\;\leq\;L^{h}_{i+1,j}.$ (7)

With this monotonicity property, we would only need to search for
$L^{h}_{i,j}$ between $L^{h}_{i,j-1}$ and $L^{h}_{i+1,j}$, thus in the
diagonal $j-i$ we search disjoint intervals. For some problems, conceivably,
this property may be true even if the quadrangle inequality is not, and it
would be in itself sufficient to speed up dynamic programming.

In this section we show, however, that this approach does not apply. We show
that the quadrangle inequality (6) is false, and that the monotonicity
property (7) is false as well. We also give counter-examples to other similar
properties that could potentially help in designing a faster algorithm.

###  5.1 Quadrangle Inequality and Minimizer Monotonicity

#### Counter-examples to quadrangle inequality.

Here is an example that the quadrangle inequality (6) does not hold in our
case. We have three ikeys $1,2,3$, with weights $1,V,1$. Let
$i=1,i^{\prime}=2=j,j^{\prime}=3$. We claim that

$\displaystyle C^{3}_{1,2}+C^{3}_{2,3}$ $\displaystyle>$ $\displaystyle
C^{3}_{1,3}+C^{3}_{2,2}.$

Indeed, $C^{3}_{1,2}=V+1$, $C^{3}_{2,3}=V+1$, while $C^{3}_{1,3}=V+4$ and
$C^{3}_{2,2}=0$. Thus the quadrangle inequality (6) is false.

This easily generalizes to larger instances. Let the keys be $1,2,...,n$, for
$n=2^{s+1}+1$. The instance consists of a block of $2^{s}$ keys of weight $1$,
followed by a key of weight $V$, followed by another block of $2^{s}$ keys of
weight $1$. Let $j=2^{s}+1$ be the key of weight $V$.

The optimum tree for an instance consisting of $2^{s}$ keys of weight $1$ is a
perfectly balanced tree and its cost is $s2^{s}$. So, if $V$ is large enough
then $C^{n}_{1,j}=C^{n}_{j,n}=V+(s+1)2^{s}$ and $C^{n}_{1,n}=V+(s+2)2^{s+1}$.
Since $C^{n}_{j,j}=0$, we then have

$C^{n}_{1,j}+C^{n}_{j,n}\;=\;2V+(s+1)2^{s+1}\;>\;C^{n}_{j,j}+C^{n}_{1,n},$

as long as $V>2^{s+1}$.

#### Counter-example to minimizer monotonicity.

We now consider (7), showing that it’s also false. Consider six keys, with the
following weights:

1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
1 | V | 1 | 1 | V | 1

where $V>8$. We claim that the unique minimizers for $C^{6}_{1,6}$ and
$C^{6}_{2,6}$ satisfy

$\displaystyle L^{6}_{1,6}\;=\;3\;>\;2\;=\;L^{6}_{2,6}.$

Indeed, we have $C^{6}_{1,3}+C^{6}_{4,6}=(V+4)+(V+4)=2V+8$ (each cost is
realized by a tree with the equal-to test for the heavy item in the root). On
the other hand, $C^{6}_{1,1}+C^{6}_{2,6}\geq 0+3V=3V$, since in any tree for
$I^{6}_{2,6}$ one heavy item will be at depth at least $2$. Also,
$C^{6}_{1,2}+C^{6}_{3,6}\geq(V+1)+(V+8)=2V+9$, because in an optimal tree for
$I^{6}_{3,6}$ the first test must be an equal-to test for the heavy item, and
the remaining items of weight $1$ will have depths at least $2,3,3$. The
remaining expressions are symmetric. Thus proves that $L^{6}_{1,6}=3$.

To show that $L^{6}_{2,6}=2$, we first compute
$C^{6}_{2,2}+C^{6}_{3,6}=0+(V+8)=V+8$. On the other hand, for $l=3,4$, we have
$C^{6}_{2,l}+C^{6}_{l,6}\geq 2V$, since each $V$ will be in a tree of size at
least $2$, while $C^{6}_{2,5}+C^{6}_{6,6}\geq 3V+0=3V$.

###  5.2 Monotonicity without Boundary Keys

We now make the following observation. In formula (2), in the cases when $l=j$
or $l=j-1$, instead of making a split with an less-than test, we can make
_equal-to_ tests to $i$ or ${j}$. But we know that, without loss of
generality, equal-to tests are made only to heaviest items. If $i$ or $j$ is
the heaviest key, then the option of doing the equal-to test will be included
in the minimum (1) anyway. If none of them is a heaviest key, then the
corresponding equal-to tests can be ignored. As a result, in (2) we can only
run index $l$ from $i+1$ to $j-2$ (and assume that $j\geq i+4$).

Motivated by this, we now introduce a definition of $S^{h}_{i,j}$, slightly
different from the one in the previous section. $S^{h}_{i,j}$ is the minimum
cost of a binary search tree with the following two properties: (i) the root
of the tree is an less-than-comparison (split node), and (ii) both the left
and the right subtree of the root has at least two nodes. Note that this
definition implies that $S^{h}_{i,j}=\infty$ whenever $|I^{h}_{i,j}|\leq 3$.

We now give a modified recurrence for $C^{h}_{i,j}$. If $|I^{h}_{i,j}|\leq 1$
then $C^{0}_{i,j}=0$. Assume $h\geq 1$ and $|I^{h}_{i,j}|\geq 2$ (in
particular, $i<j$). If $a_{h}\notin I^{h}_{i,j}$, then
$C^{h}_{i,j}=C^{h-1}_{i,j}$, because in this case $I^{h}_{i,j}=I^{h-1}_{i,j}$.
So assume now that $a_{h}\in I^{h}_{i,j}$. Then:

$\displaystyle C^{h}_{i,j}\;$
$\displaystyle=\;w^{h}_{i,j}+\min{\left\\{{C^{h-1}_{i,j},S^{h}_{i,j}}\right\\}},\quad\textrm{where}$
(8) $\displaystyle S^{h}_{i,j}\;$
$\displaystyle=\;\min_{l=i+1,...,j-2}{\left\\{{C^{h}_{i,l}+C^{h}_{l+1,j}}\right\\}}.$
(9)

The earlier counter-example does not apply to this new formulation, because
now we only need the minimizer monotonicity to hold between locations $l=i+1$
and $l=j-2$. (The counter-example to the quadrangle inequality is technically
correct, but it does not seem to matter for our new definition.)

#### Counter-example.

This does not work either. Consider the example below.

1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
0 | 2 | 2 | 0 | 1 | 1

We claim that the minimizer monotonicity is violated in this example. Recall
that $L^{h}_{i,j}$ is the minimizer for $S^{h}_{i,j}$, namely the index
$l\in{\left\\{{i+1,...,j-2}\right\\}}$ such that
$S^{h}_{i,j}=C^{h}_{i,l}+C^{h}_{l+1,j}$. (Note that now we don’t allow values
$l=i$ and $l=j-1$.) To get the amortization to work, it would be enough to
have

$\displaystyle L^{h}_{i,j-1}\;\leq\;L^{h}_{i,j}\;\leq\;L^{h}_{i+1,j}.$

We show that this inequality is false. In this example we have
$L_{1,6}=4>3=L_{2,6}$. (Below we use $h=6$ in all expressions, so we will omit
it.)

To prove this, let’s consider $L_{1,6}$ first. For $l=2$ we have
$C_{1,2}+C_{3,6}=2+7=9$. For $l=3$ we have $C_{1,3}+C_{4,6}=6+3=9$. For $l=4$
we have $C_{1,4}+C_{5,6}=6+2=8$. Thus $L_{1,6}=4$, as claimed.

Next, consider $L_{2,6}$. For $l=3$ we have $C_{2,3}+C_{3,6}=4+3=7$. For $l=4$
we have $C_{2,4}+C_{5,6}=6+2=8$. Thus $L_{2,6}=3$, as claimed.

Note also that this example remains valid even if we don’t restrict $l$ to be
between $i+1$ and $j-2$. For $L_{1,6}$, we have that $C_{1,1}+C_{2,6}$ and
$C_{1,5}+C_{6,6}$ are at least $9$. For $L_{2,6}$, we get that
$C_{2,2}+C_{3,6}=7$ and $C_{2,5}+C_{6,6}=9$, so $l=2$ is tied with $l=3$. But
we can break the tie to make $l=3$ by slightly increasing the weight of key
$6$ to $1+\epsilon$, for some small $\epsilon>0$.

###  5.3 Monotonicity For Constant Weights

So far, our counter examples have used relatively unbalanced weights. Suppose
that the weights were bounded in the range ${\left[{1,R}\right]}$, where $R$
is constant relative to $n$. For sufficiently large $n$, most of the
comparisons in the search tree would have to be less-than tests, except with a
few equal-to tests near the bottom. A natural conjecture would be that these
perturbations near the bottom would not affect global structural properties of
an optimal tree, and that the quadrangle inequality could only fail for some
constant number of diagonals near the main diagonal. As it turns out, this is
false.

#### Counter-example.

Consider an instance of $n$ keys with a repeating pattern of weights
${\left({1,3,1,3,\ldots}\right)}$, going from left to right. We claim without
proof that if $n$ is an even number between $2^{p+1}+2$ and $3\cdot 2^{p}$ for
$p\geq 2$, we have

$C_{1,n-1}^{n}+C_{2,n}^{n}=C_{2,n-1}^{n}+C_{1,n}^{n}+1.$

Furthermore, we claim that $L_{2,n}^{n}=L_{3,n}^{n}+1$ for even $n$ in
${\left[{2^{p+1}+2,5\cdot 2^{p-1}}\right]}$ and $L_{1,n}^{n}=L_{1,n-1}^{n}-1$
for even $n$ in ${\left[{5\cdot 2^{p-1}+2,3\cdot 2^{p}}\right]}$. We have
computationally verified these claims for $p\leq 8$. Intuitively, these
instances correspond to balanced trees, where sub-trees rooted at equal-to
tests are at the bottom. As shown in Figure 4, these bottom sub-trees are the
only things that change when we remove the boundary keys. Therefore the
difference in cost, no matter the size of the tree, comes down to comparing
the costs of small sub-trees, where equal-to tests are optimal and break
monotonicity.

We also remark that this counter-example is not unique. Weight patterns like
${\left({1,2,3,1,2,3,\ldots}\right)}$ and
${\left({3,1,1,3,1,1,\ldots}\right)}$ yield similar results. In fact,
monotonicity can break even by simply generating random integers in
${\left[{1,R}\right]}$, albeit in a less regular pattern. Figure 5 illustrates
some examples. Despite that, the error in monotonicity or the quadrangle
inequality appears to be consistently small and not scale with $n$, suggesting
that instances with constant weights may have an “approximate monotonicity”
property that could still speed up the DP algorithm.

(a) $I_{1,24}^{24}$, $\text{cost}=216$

(b) $I_{2,23}^{24}$, $\text{cost}=193$

(c) $I_{1,23}^{24}$, $\text{cost}=200$

(d) $I_{2,24}^{24}$, $\text{cost}=210$

Figure 4: Optimal trees for the 24-key instance with weight pattern
${\left({1,3,1,3,\ldots}\right)}$. $A$, $B$, and $C$ are sub-trees, where $A$
handles an instance with weights ${\left({1,3,1}\right)}$, $B$ handles
${\left({3,1,3}\right)}$, and $C$ handles ${\left({1,3,1,3}\right)}$. Note
that keys used in less-than tests, which are omitted from the figures, are
different across these instances.

(a) ${\left({1,3,1,3,\ldots}\right)}$

(b) ${\left({3,1,2,3,1,2,\ldots}\right)}$

(c) Random weights in ${\left\\{{1,2,3}\right\\}}$

Figure 5: “QI tables” for various weight patterns. The pixel $i$ rows down and
$j$ columns to the right corresponds to $I_{i,j}^{n}$, where $n=192$. We color
$I_{i,j}^{n}$ gray if $C_{i+1,j}^{n}+C_{i,j-1}^{n}\leq
C_{i+1,j-1}^{n}+C_{i,j}^{n}$ or red if otherwise.

###  5.4 Monotonicity Along Diagonals

Earlier we disproved the minimizer monotonicity property stating that
$L^{h}_{i,j-1}\leq L^{h}_{i,j}\;\leq\;L^{h}_{i+1,j}$. In this property, the
minimizers along the diagonal $d=j-i$ are sandwiched between the minimizers
for the previous diagonals. A weaker condition would be to require that that
minimizers increase along any given diagonal:

$L^{h}_{i,j}\;\leq\;L^{h}_{i+1,j+1}$

We remark that this property does not necessarily imply a faster algorithm.

#### Counter-example.

We now show that this property also fails. Consider the example below. (This
is a minor modification of the example in the previous section.)

1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---
$\epsilon$ | 2 | 2 | 0 | 1 | 1 | 0

Here, $\epsilon>0$ is very small. The same argument as in the previous section
gives us that $L_{1,6}=4$. (The value of $C_{1,4}+C_{5,6}$ will be
$8+O(\epsilon)$ while for other splits the values are at least $9$.) s We now
claim that $L_{2,7}\leq 3$. We consider the split values $l=2,3,4,5,6$. For
$l=2$, $C_{2,2}+C_{3,7}\geq 11$. For $l=3$, $C_{2,3}+C_{4,7}\leq 7$. For
$l=4$, $C_{2,4}+C_{5,7}\geq 9$. For $l=5$, $C_{2,5}+C_{6,7}\geq 10$. For
$l=6$, $C_{2,6}+C_{7,7}\geq 13$. So $L_{2,7}=3$.

Therefore we have $L_{1,6}=4>3=L_{2,7}$, showing that the minimizers are not
monotone along the diagonals of the dynamic programming table.

#### Counter-example.

In the above example, the _optimum tree_ would actually start with an equal-to
test. To refine it, we take a step forward and present an instance where a
less-than test in the root is necessary, while the minimizers still do not
meet the condition of monotonicity along the diagonals. The assigned weights
are as follows.

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---
12 | 10 | 3 | 9 | 8 | 2 | 6 | 7 | 5 | 1 | 11 | 13

Now we examine the 2wcst’s of $I_{1,11}^{12}$ and $I_{2,12}^{12}$. It can be
simply verified that in both of these instances, the weight of the heaviest
item is less than $\frac{1}{4}$ of the total weight of the items. Thus,
following Theorem 3.1 (by Anderson et al. [1]), we observe that every 2wcst
should starts with a less-than test. Additionally, this example has another
interesting property: For each $l\in\\{2,3,\dots,10\\}$, there exists a 2wcst
for $I_{1,l}^{12}$ and $I_{l+1,12}^{12}$ that initiates with less-than test.
The same thing holds for $I_{2,12}^{12}$, which makes this set of items quite
balanced. However, we have $L_{1,11}^{12}=6>5=L_{2,12}^{12}$ and these
minimizers are unique. This leads to a counter-example where the monotonicity
of minimizers along the diagonals is violated (this result can be verified
computationally). Figure 6 illustrates 2wcst’s of $I_{1,11}^{12}$ and
$I_{2,12}^{12}$.

(a) 2wcst of $I_{1,11}^{12}$, $L_{1,11}^{12}=6$

(b) 2wcst of $I_{2,12}^{12}$, $L_{2,12}^{12}=5$

Figure 6: Illustration of (a) $I_{1,11}^{12}$ and (b) $I_{2,12}^{12}$ in
Section 5.4.

###  5.5 Marginal Advantage of Equal-to Tests

Suppose that the heaviest key in $[i,j]$ is in a subinterval
$[i^{\prime},j^{\prime}]\subsetneq[i,j]$. And suppose that for
$[i^{\prime},j^{\prime}]$ the optimum choice is a less-than test. Does it
necessarily imply that the optimum choice for $[i,j]$ is also a less-than
test? Intuitively, that would show that the marginal advantage of equal-to
tests (by how much they are better than the best less-than test) decreases
when the interval gets bigger. That’s quite intuitive, since the relative
weight of this key to the total weight of the interval gets smaller, so it is
less likely to be used by the optimum tree in an equal-to test. (This is also
consistent with the threshold result in Theorem 3.1: If the weight of the
heaviest key becomes smaller than $\tfrac{1}{4}$ of the total interval weight,
then the tree uses a less-than-test.) We show that this intuition is not
valid.

#### Counter-example.

Let $\alpha=11$, $\alpha^{\prime}=13$, and $\beta=23$. Consider the following
instance:

1 | 2 | 3 | 4 | 5
---|---|---|---|---
$\alpha$ | $\beta$ | $\beta$ | $\alpha^{\prime}$ | $0$

For the smaller instance $[1,4]$ the optimum values for the equal-to test and
the less-than test are

$C^{=}_{1,4}\;=\;\beta+3\beta+4(\alpha+\alpha^{\prime})\;=\;141\quad\textrm{and}\quad
C^{<}_{1,4}\;=\;C^{<}_{1,4}(2)\;=\;2(2\beta+\alpha+\alpha^{\prime})\;=\;140.$

For the larger instance $[1,5]$ the optimum values for the equal-to test and
the less-than test are

$C^{=}_{1,5}\;=\;\beta+3\beta+3\alpha^{\prime}+4\alpha\;=\;152\quad\textrm{and}\quad
C^{<}_{1,5}\;=\;C^{<}_{1,5}(2)\;=\;2(2\beta+\alpha)+3\alpha^{\prime}\;=\;153.$

So we have $C^{=}_{1,4}>C^{<}_{1,4}$, but $C^{=}_{1,5}<C^{<}_{1,5}$.

(a) $C_{1,4}^{=}$

(b) $C_{1,4}^{<}$

(c) $C_{1,5}^{=}$

(d) $C_{1,5}^{<}$

Figure 7: Illustration of the counter-example in Section 5.5.

###  5.6 Bounding Dynamic-Programming Minimizers by Weight

Corollary 3.3 provides a potential algorithmic improvement as it extends [1]’s
thresholds to less-than tests. More specifically it implies that the minimizer
$l=L_{i,j}^{h}$ has to satisfy
$\min{\left\\{{w_{i,l}^{h},w_{l+1,j}^{h}}\right\\}}\geq\tfrac{1}{4}w_{i,j}^{h}$.
In other words, for any optimal tree rooted at a less-than test, the left and
right branches of the root are relatively balanced, in the sense that the
smaller branch is at least one fourth of the instance’s total weight. A simple
modification is to only search for minimizers where the side-weight is at
least $\frac{1}{4}w_{i,j}^{h}$.

For a given sub-problem $I_{i,j}^{h}$, the “refined interval”
$\mathcal{I}_{i,j}^{h}$ is defined as the set

$\mathcal{I}_{i,j}^{h}={\left\\{{i\leq
l<j{\;:\;}sw_{i,j}^{h}{\left({l}\right)}\geq\tfrac{1}{4}w_{i,j}^{h}}\right\\}}$

where
$sw_{i,j}^{h}{\left({l}\right)}=\min{\left\\{{w_{i,l}^{h},w_{l+1,j}^{h}}\right\\}}$.

From Corollary 3.3, $L_{i,j}^{h}$ must be in $\mathcal{I}_{i,j}^{h}$. We can
show that $\mathcal{I}_{i,j}^{h}$ is always an interval with no holes. By
increasing the cut-point $l$, the left-branch increases in weight and the
right-branch decreases. So if $l\in\mathcal{I}_{i,j}^{h}$ but
$l+1\notin\mathcal{I}_{i,j}^{h}$, then the right branch is the side-branch of
$l+1$, and moving the cut-point further right only decreases the side-weight
as the right-branch gets smaller. Likewise happens for moving cut-points left.
We can then represent each interval with end points
$\mathcal{I}_{i,j}^{h}=[a_{i,j}^{h},b_{i,j}^{h}]$. By pre-computing these
intervals (or even computing them on an ad hoc basis in the recurrence) we can
potentially narrow the number of sub-problems in the dynamic programming
algorithm.

######  Observation 5.1.

For an instance of $n$ keys, the set of refined intervals can be computed in
$O{\left({n^{3}\log n}\right)}$ time.

###### Proof.

The algorithm is straightforward. We first compute the weights of each sub-
problem in $O{\left({n^{3}}\right)}$ time in the standard fashion. Then for
each sub-problem $I_{i,j}^{h}$, we perform three rounds of binary search.

First, we find one element $c\in\mathcal{I}_{i,j}^{h}$, if there is any. To do
this, we select the midpoint $m$ of ${\left[{i,j-1}\right]}$ and check if
$sw_{i,j}^{h}{\left({m}\right)}\geq\frac{1}{4}w_{i,j}^{h}$. If yes, then we
are done. If not, we check which branch of the cut-point $m$ is lighter. If
the left branch is lighter, we search in the interval
${\left[{m+1,j-1}\right]}$, as we need to move the cut point right to make the
branch heavier. Likewise, we search in the interval ${\left[{i,m-1}\right]}$
if the right branch is lighter. We continue until we converge to a single cut-
point, and if said point’s side weight is still too light, then $R_{i,j}^{h}$
is empty and we are done.

If we found a cut-point $c\in\mathcal{I}_{i,j}^{h}$, we use binary search for
each end point $a_{i,j}^{h}$ and $b_{i,j}^{h}$. To find the lower bound, we
start searching in the interval ${\left[{i,c}\right]}$. We select the midpoint
$m$ and check if $sw_{i,j}^{h}{\left({m}\right)}\geq\frac{1}{4}w_{i,j}^{h}$.
If no, then we search in ${\left[{m+1,c}\right]}$. If yes, we then check if
$sw_{i,j}^{h}{\left({m-1}\right)}\geq\frac{1}{4}w_{i,j}^{h}$. If no (or if
$m-1<i$), then $m$ is our lower bound and we are done. If yes, then search in
${\left[{i,m-1}\right]}$. The search works similarly for the upper bound. ∎

Notably, refined intervals may still be large in proportion to the interval
${\left[{i,j-1}\right]}$ (if all keys have the same weight, then
${\left|{\mathcal{I}_{i,j}^{h}}\right|}=\textstyle{\frac{1}{2}}{\left({j-i+1}\right)}$),
so they can’t significantly cut down on the time it takes to find minimizers.
However, they may significantly reduce the number of necessary sub-problems we
need to compute. Consider a modified recurrence which uses refined intervals
and also the two heaviest-key thresholds $\lambda^{-}$ and $\lambda^{+}$:

$\displaystyle C_{i,j}^{h}$
$\displaystyle=w_{i,j}^{h}+\begin{cases}C_{i,j}^{h-1},&\text{if }a_{h}\in
I_{i,j}^{h}\text{ and }w_{a_{h}}\geq\tfrac{3}{7}w_{i,j}^{h},\\\
S_{i,j}^{h},&\text{if }a_{h}\in I_{i,j}^{h}\text{ and
}w_{a_{h}}<\tfrac{1}{4}w_{i,j}^{h},\\\
\min{\left\\{{C_{i,j}^{h-1},S_{i,j}^{h}}\right\\}},&\text{else.}\end{cases}$
$\displaystyle S_{i,j}^{h}$
$\displaystyle=\min_{l\in\mathcal{I}_{i,j}^{h}}{\left\\{{C_{i,l}^{h}+C_{l+1,j}^{h}}\right\\}}.$

In this recurrence, we consider only one type of comparison test when
$w_{a_{h}}$ hits a certain threshold and limit the cut-points we consider for
less-than tests.

#### Counter-example.

Consider the $n$-key instance with weights

$\displaystyle(X_{1}$
$\displaystyle,G,X_{2},G,X_{3},G,X_{0}),\quad\text{where}$ $\displaystyle
X_{k}$
$\displaystyle={\left({\gamma^{4i+k}}\right)}_{i=0}^{n/7-1}={\left({\gamma^{k},\gamma^{4+k},\ldots,\gamma^{n/7-1+k}}\right)},$
$\displaystyle G$ $\displaystyle={\left({0}\right)}_{i=1}^{n/7}.$

Visually, we have a geometric sequence distributed modulo $4$ into smaller
sub-sequences, with some “garbage” $G$ in between. Here we’ll fix
$\gamma=\tfrac{3}{4}$. Then the total weight of this instance is $4-\epsilon$,
where $\epsilon$ can be made arbitrarily small by considering larger $n$.
We’ll show that the recurrence defined above creates
$\Omega{\left({n^{3}}\right)}$ sub-problems that take
$\Omega{\left({n}\right)}$ time to compute. We do this by considering “rounds
of decisions”.

For this instance, the heaviest weight is $1$, slightly above $\tfrac{1}{4}$
the total. In which case the recurrence has to consider both equal-to tests
and less-than tests. This case occurs even after taking several equal-to
tests, so long as we don’t take too many. And after taking four equal-to tests
(one from each $X_{i}$), we have an identical instance, but with slightly
fewer keys, whose weights are scaled by $\gamma$. In our first round, remove
some fraction of keys using equal-to tests to generate
$\Omega{\left({n}\right)}$ sub-problems, each comparable to the original
instance but scaled by some $\gamma^{i}$. The exact fraction of $n$ keys
doesn’t matter, so long as the heaviest weight is still approximately
$\tfrac{1}{4}$ the total weight of each sub-problem.

In the second round, for each sub-problem from round 1, the keys corresponding
to $X_{0}$ makes up about $1-\gamma^{4}\approx 0.684$ of the total weight.
This means all of the cut-points in the garbage $G$ between $X_{0}$ and
$X_{3}$ are plausible cuts in the sub-problem’s refined interval. Then for
each round 1 sub-problems, the recurrence must consider at least $n/7$ sub-
problems corresponding to less-than tests in this garbage region. This creates
$\Omega{\left({n^{2}}\right)}$ round 2 sub-problems.

In the third round, for each sub-problem from round 2, weights are comprised
of keys from $X_{1}$, $X_{2}$, and $X_{3}$. Factoring out the $\gamma^{i}$
term created from round 1, each sub-problem has heaviest weight $\gamma$ and
approximate total weight $w\approx 4-1/{\left({1-\gamma^{4}}\right)}$ . In
which case the heaviest weight takes approximately $\gamma/w\approx 0.296$ of
the total weight, still between $\tfrac{1}{4}$ and $\tfrac{3}{7}$. So each
sub-problem still needs to consider less-than tests. The keys in $X_{1}$ have
weight about $\gamma/{\left({1-\gamma^{4}}\right)}\approx 0.432$ , so all of
the keys in the garbage $G$ between $X_{1}$ and $X_{2}$ are in the refined
interval. So each round 2 sub-problem generates at least $n/7$ sub-problems
corresponding to these cut-points.

We now have $\Omega{\left({n^{3}}\right)}$ sub-problems, each containing keys
from $X_{2}$ or $X_{3}$ surrounded by zero-weight keys from the leftmost and
rightmost garbage regions. Ignoring the $\gamma^{i}$ term from round 1, the
heaviest weight is $\gamma^{2}$ and total weight approximately
$w=4-(1+\gamma)/(1-\gamma^{4})$ . The heaviest weight is then about
$\gamma/w\approx 0.391$ of the total weight, still between $\tfrac{1}{4}$ and
$\tfrac{3}{7}$. Then keys in $X_{3}$ have weight about
$\gamma^{2}/(1-\gamma^{4})$ , making about $0.571$ of the total weight. So the
garbage between $X_{2}$ and $X_{3}$ are cut-points in the refined interval,
and thus each round 3 sub-problem needs to evaluate $n/7$ cut-points, taking
$\Omega{\left({n}\right)}$ time to compute. Therefore this instance takes
$\Omega{\left({n^{4}}\right)}$ time to compute.

##  6 Algorithms for Bounded Weights

In this section we show that if the ratio between the largest and smallest
weight is $R$ then the optimum can be computed in time $O(n^{3}\log(nR))$. We
can assume that the weights are from the interval $[1,R]$.

Constant $R$. Let’s start with the case when $R$ is constant. If $j-i+1>4R$
then the maximum weight in $[i,j]$ will be less than $\frac{1}{4}$th of the
total weight of $I^{n}_{i,j}$ (the total weight of interval $[i,j]$). By
Theorem 3.2 (see [1]), the optimum tree will use a less-than test. In other
words, for intervals $[i,j]$ with $j-i+1>4R$ we do not need to consider
instances with holes (the keys from $[i,j]$ that are not in the instance). The
optimum cost for this interval is $C_{i,j}=C^{n}_{i,j}=S^{n}_{i,j}$. So the
algorithm can do this: (1) compute all optimal solutions $C_{i,j}$ for the
diagonals with $j-i+1\leq 4R$ even by brute force (as they have each constant
size), and then (2) for the remaining diagonals use the recurrence
$C_{i,j}=\min_{l=i,...,j-1}{\left\\{{C_{i,l}+C_{l+1,j}}\right\\}}$. This gives
us an $O(n^{3})$-time algorithm.

Arbitrary $R$. We now sketch an algorithm for $R$ that may be a growing
function of $n$. (We assume that $R\leq c^{n}$ for some $c$. Otherwise this
algorithm will not beat $O(n^{4})$.)

Consider an instance $I^{h}_{i,j}$. Recall that the keys in $[i,j]$ that are
not in $I^{h}_{i,j}$ are called _holes_. All holes in $I^{h}_{i,j}$ are
heavier than non-holes. The naive dynamic programming considers instances
$I^{h}_{i,j}$ with any number of holes, that is $0\leq|I^{h}_{i,j}|\leq
j-i+1$. The idea is that we only need to consider holes that are sufficiently
heavy.

Represent each sub-problem slightly differently: by its interval $[i,j]$ and
the number of holes $s$. Denote by $v^{s}$ the weight of the instance for
interval $[i,j]$ from which $s$ holes have been removed. We have that
$v^{0}\leq nR$, and Theorem 3.2 gives us that we only need to remove the $s$th
hole if its weight is at least $\tfrac{1}{4}$th of the total weight of the
interval $[i,j]$ with $s-1$ holes already removed. (Otherwise, the optimum
tree for this sub-instance has the less-than test, so the sub-instances with
more holes in this interval do not appear in the overall optimal solution.)
This implies that $v^{s}\leq\tfrac{3}{4}\cdot v^{s-1}$. If we thus remove $t$
holes, we will get $v^{t}\leq(\tfrac{3}{4})^{t}\cdot nR$. But since all
weights are at least $1$, this implies that $t=O(\log(nR))$.

Summarizing, we only need to consider sub-problems parametrized by $[i,j]$ and
$s\leq\log(nR)$. This gives us $O(n^{2}\log(nR))$ instances and the running
time $O(n^{3}\log(nR))$.

## References

  * [1] R. Anderson, S. Kannan, H. Karloff, and R. E. Ladner.  Thresholds and optimal binary comparison search trees.  Journal of Algorithms, 44:338–358, 2002.
  * [2] Sunny Atalig and Marek Chrobak.  A tight threshold bound for search trees with 2-way comparisons.  in preparation, 2023.
  * [3] Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, and Yan Zhang.  The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.  ACM Trans. Algorithms, 6(1):17:1–17:22, 2009.
  * [4] Marek Chrobak, Mordecai Golin, J. Ian Munro, and Neal E. Young.  A simple algorithm for optimal search trees with two-way comparisons.  ACM Trans. Algorithms, 18(1):2:1–2:11, December 2021.
  * [5] Marek Chrobak, Mordecai Golin, J. Ian Munro, and Neal E. Young.  On Huang and Wong’s algorithm for generalized binary split trees.  Acta Informatica, 59(6):687–708, December 2022.
  * [6] D. E. Knuth.  Optimum binary search trees.  Acta Informatica, 1:14–25, 1971.
  * [7] D. Spuler.  Optimal search trees using two-way key comparisons.  Acta Informatica, 31(8):729–740, 1994.
  * [8] D. A. Spuler.  Optimal search trees using two-way key comparisons.  PhD thesis, James Cook University, 1994.
  * [9] F. Frances Yao.  Efficient dynamic programming using quadrangle inequalities.  In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 429–435. ACM, 1980.