## 7 Analysis
### The Number of Edges Scanned  
We now examine the impact of edge scans more closely. Figure 10 shows the average number of non-tree edges, as a function of \(M_{\mathcal{P}}\), actually scanned by FCT(0) when operating on complete sets of rooted triples. Observe that not only does the number of edge scans increase at an only slightly super-linear rate, but also the average number of non-tree edges scanned is considerably smaller than \(M_{\mathcal{P}}\). Together with Theorem 1, this explains the near-\(\mathcal{O}(M_{\mathcal{P}}\log M_{\mathcal{P}})\) behavior seen in Figure 7.  
Figure 11 shows the average number of non-tree edges actually scanned by FCT(0) on profiles of binary phylogenies. The input profiles were generated as described in Section 5.4. As in that section, we varied one of \(n\), the number of labels, or \(k\), the number of trees, while keeping the other quantity fixed, and we took the product \(n\times k\) as a proxy for \(M_{\mathcal{P}}\).  
When \(n\) was fixed, the number of non-tree edges scanned was roughly proportional to \(M_{\mathcal{P}}\), suggesting that the running time of FCT(0) was \(\mathcal{O}(M_{\mathcal{P}}\log M_{\mathcal{P}})\). This is reflected in Figure 8a. On the other hand, when \(k\) was fixed, the number of non-tree edges scanned appeared to grow in a slightly super-linear manner. The explanation appears to be that increasing \(k\) increased the amount of overlap among the trees, and consequently also the number of non-tree edges. Nevertheless, the overall running time of FCT(0) in this case appeared close to \(\mathcal{O}(M_{\mathcal{P}}\log M_{\mathcal{P}})\); see Figure 8b. This may  
\begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & **5\%** & **10\%** & **15\%** & **20\%** & **25\%** & **30\%** & **35\%** & **40\%** & **45\%** & **50\%** \\ \hline \(\mathit{Num}(\mathit{NTE})\) & 97.80\% & 97.69\% & 97.58\% & 97.37\% & 97.24\% & 97.11\% & 96.88\% & 96.62\% & 96.39\% & 96.07\% \\ \(\mathit{Time}(\mathit{NTE})\) & 68.38\% & 67.74\% & 67.17\% & 66.15\% & 65.99\% & 65.05\% & 64.53\% & 63.25\% & 62.74\% & 61.73\% \\ \hline \hline \end{tabular}
\end{table}
Table 10: FPP(0) on high-density matrices of order \(300\times 6000\): Ratio of number of deleted non-tree edges to total number of edges and ratio of time spent on deleting non-tree edges to total HDT execution time.  
Figure 10: Number of non-tree edges scanned by FCT(0) for complete sets of rooted triples.  
\begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & **5\%** & **10\%** & **15\%** & **20\%** & **25\%** & **30\%** & **35\%** & **40\%** & **45\%** & **50\%** \\ \hline \(\mathit{Num}(\mathit{TEE})\) & 88.78\% & 88.28\% & 87.57\% & 87.03\% & 86.32\% & 85.00\% & 83.87\% & 82.61\% & 82.12\% & 79.89\% \\ \(\mathit{Time}(\mathit{NTE})\) & 56.36\% & 54.65\% & 54.61\% & 55.24\% & 53.33\% & 52.79\% & 52.84\% & 51.24\% & 50.24\% & 49.78\% \\ \hline \hline \end{tabular}
\end{table}
Table 9: FPP(0) on medium-density matrices of order \(300\times 6000\): Ratio of number of deleted non-tree edges to total number of edges and ratio of time spent on deleting non-tree edges to total HDT execution time.  
be because the effect of increasing the number of non-tree edges was mitigated by another factor: the sizes of the smaller of two subtrees resulting from edge deletion.  
Table 11 reports the number of non-tree edges scanned throughout the execution of FPP(0). Overall, the number of scanned non-tree edges was smaller than the total number of edges. This again illustrates that searching for replacement edges did not significantly contribute to the running time. Surprisingly, the largest number of edge scans occurred for medium-density matrices. We have not found a satisfactory explanation for this observation.