# Efficient Approaches to the Mixture Distance Problem
## 3 An \(O(nh_{1}h_{2})\)-Time Algorithm
### Modified Algorithm
: _An example of constructing the subtree \(T_{2}^{\prime}\) with respect to \(leaf(v_{2})=\{A,B,G,H\}\) is illustrated in Figure 3. Initially, the node set \(V^{\prime}\) is \(\{A,B,lca(A,B)\}\) and the edge set \(E^{\prime}\) includes the incident edges of the three nodes in \(T_{2}\). As node \(A\) is processed, two nodes \(lca(B,G)\) and \(G\) are inserted into \(V^{\prime}\), and two edges \(\overline{lca(A,B)lca(B,G)}\) and \(\overline{lca(B,G)G}\) are inserted into \(E^{\prime}\). Later, when node \(B\) is processed, two nodes \(lca(G,H)\) and \(H\) are inserted into \(V^{\prime}\) and two edges \(\overline{lca(B,G)lca(G,H)}\) and \(\overline{lca(G,H)H}\) are inserted into \(E^{\prime}\). Meanwhile, the edge \(\overline{lca(B,G)G}\) is removed from \(E^{\prime}\) and the edge \(\overline{lca(G,H)G}\) is inserted into \(E^{\prime}\), because the mutation time of \(lca(B,G)\) is larger than the time of the \(lca(G,H)\)._  
After the subtree \(T_{2}^{\prime}\) with respect to currently processed node \(v\) is constructed, stage 3 of the algorithm performs lines 5-18 of Algorithm MixtureDistance to compute the \"partial\" mixture distance between \(T_{2}^{\prime}\) and the subtree rooted by \(v\) (only computes the distances of some nodes pairs, for which LCA is equal to \(v\)). At the end of the algorithm, \(\mathcal{D}\) indicates the mixture distance between \(T_{1}\) and \(T_{2}\). **Theorem 2**. : _The improved algorithm takes \(O(nh_{1}h_{2})\) computational time and \(O(n)\) preprocessing time, where \(n\) denotes the number of leaves of the mixture trees and \(h_{i}=height(T_{i})\) for \(i=1,2\)._  
Proof. : The algorithm contains three main stages. The first stage ranks the leaves in \(T_{1}\) and \(T_{2}\), which takes \(O(n)\) time. In the second stage, a minimal subtree \(T_{2}^{\prime}\) of \(T_{2}\) involved in colored leaves with respect to each node \(v\) in \(T_{1}\) is constructed. For each node \(v\), a leaf list \(leaf(v)\) is obtained from the leaf lists of its two children, which is achieved in \(O(t)\) time by using the two-way merging algorithm [23] performed on the leaf list of \(v\)'s children, where \(t\) is the size of \(leaf(v)\). The \(O(1)\)-time algorithm with \(O(n)\)-time processing [21] is employed to compute the LCA of any pair of nodes in \(T_{2}\). Constructing \(T_{2}^{\prime}\) takes \(O(th^{\prime})\) time, where \(h^{\prime}\) is the height of \(T_{2}^{\prime}\) due to the \"repeat\" step. The last stage computes the mixture distance between \(v\) and each internal node in \(T_{2}^{\prime}\) by performing lines 5-18 of Algorithm MixtureDistance, which takes \(O(t)\) time. Stages 2 and 3 take \(O(n)\) iterations in total. However, each iteration deals with different \(t\) nodes. Note that for all internal nodes which are in the same level of \(T_{1}\), the sum of \(t\) (for each node) is \(n\). Therefore, stages 2 and 3 totally take \(O(nh_{1}h^{\prime})=O(h_{1}h_{2})\) time, where \(h_{1}\) is the height of \(T_{1}\) (note that \(h^{\prime}\leq h_{2}=height(T_{2})\)). Hence, the algorithm requires \(O(nh_{1}h_{2})\) computational time with \(O(n)\) preprocessing time.