## 7 Analysis
In particular, if the input profile consists of binary trees, the time is_ \(\mathcal{O}(|V(T)|\cdot\log M_{\mathcal{P}})\)_._
2. _Suppose_ \(d_{v}=2\) _and that_ \(e\) _is the first edge incident on_ \(v\) _that is deleted. Let_ \(e^{\prime}\) _be the other edge incident on_ \(v\)_. Then, at the time of deletion,_ \(e^{\prime}\) _is a tree edge, and deleting it takes_ \(\mathcal{O}(\log M_{\mathcal{P}})\) _time._  
Proof. : (1) Part (a) was noted in Section 2.2.2. For Part (b) observe that if \(e\) is the only tree edge incident on \(v\), then deleting \(e\) leaves \(v\) as an isolated node in the spanning forest; i.e, as a component of size one, and, hence, as the smaller component. Any non-tree edge incident on \(v\) must be a replacement edge, and, if such an edge is found, it takes \(\mathcal{O}(\log M_{\mathcal{P}})\) time to re-link \(v\) to the rest of the forest. Part (c) follows from Lemma 2 and the fact that there are at most \((\genfrac{|V(T)|}{2}{|V(T)|}-(|V(T)|-1)\) edges with both endpoints incident in \(T\). The claim for profiles of binary trees follows by noting that \(d_{uv}\leq 2\) for every node \(w\). (2) There are two cases. If \(e^{\prime}\) was a tree edge before deleting \(e\), then \(e^{\prime}\) remains a tree edge after the deletion of \(e\). If \(e^{\prime}\) is a non-tree edge before deleting \(e\), then \(e^{\prime}\) must be used as a replacement edge during the deletion of \(e\), so \(e^{\prime}\) becomes a tree edge. \(\mathrm{HDT}(0)\) deletes \(e^{\prime}\) by first splitting, in \(\mathcal{O}(\log M_{\mathcal{P}})\) time, the ET-tree that contains both endpoints of \(e^{\prime}\). This leaves vertex \(v\) as the sole element in the smaller component, after which the vertex \(v\) is simply discarded. Proposition 2 points to three key issues that affect the performance of HDT(0) when used in either BuildNT or PPSS: the number of non-tree edge deletions, the number of tree edge deletions, and the size of the smaller components resulting from tree edge deletions. For profiles consisting of binary phylogenetic trees (including profiles of triples), Proposition 2(2) implies that at least half of HDT(0)'s tree-edge deletions take \(\mathcal{O}(\log M_{\mathcal{P}})\) time in the worst case. This is faster than the amortized time they take when performed by HDT. Proposition 2(1) notes the downside: the other half of the deletions could be expensive. These observations hold to some extent for profiles consisting of trees of small degree, although the ratio of inexpensive to expensive tree-edge deletions goes down. On the other hand, for larger degree trees, and in particular for the denser inputs generated by IDPP, non-tree edges are relatively abundant. As indicated in Proposition 2(1a), such edges are trivial to delete. Proposition 2(1c) implies that if the majority of the smaller components resulting from tree edge deletions are very small, then the time that HDT(0) spends on maintaining connectivity information throughout the execution of BuildNT (or PPSS) will also be small. More precisely, let \(e_{1},\ldots,e_{\ell}\) be the successive tree edges deleted by BuildNT (or PPSS), and let \(N_{i}=\min\{|V(t_{i})|^{2},\sum_{u\in V(t_{i})}d_{uv}\}\), where \(t_{i}\) is the smaller of the two trees of HDT(0)'s spanning forest created by deleting \(e_{i}\). Then, the total time spent in all tree edge deletions is \(\mathcal{O}(\sum_{i=1}^{\ell}N_{i}\cdot\log M_{\mathcal{P}})\). If, for instance, \(\sum_{i=1}^{\ell}N_{i}=\mathcal{O}(M_{\mathcal{P}}\log M_{\mathcal{P}})\), then the total time to maintain connectivity information (including the total time for non-tree edge deletions, which take \(\mathcal{O}(1)\) time each) would be \(\mathcal{O}(M_{\mathcal{P}}\log^{2}M_{\mathcal{P}})\), matching the behavior we observed in Section 5. In the next sections, we examine separately the three key factors affecting the performance of HDT(0) on BuildNT and PPSS. Section 7.1 studies the impact of deletion of non-tree edges on overall performance.