Comparisons with earlier algorithms on random and r8s trees. The running time for the new algorithm compared to the existing O(n2d2) and O(n3) time algorithms for random and r8s trees. The lines are fitted polynomial c. n2, for the case of the new algorithm (denoted n2d in the legend) and the O(n2d2) algorithm, and the polynomial c. n3 for the O(n3) algorithm. The plot is in log-scale on both the x- and y-axis.