The quartet distance is a way of measuring the distance between two phylogenetic trees. It is defined as the number of subsets of four leaves that are not related by the same topology in both trees.
Computing the quartet distance
The most straightforward computation of the quartet distance would require
For binary trees, better algorithms have been found to compute the distance in
and
Brodal et al. found an algorithm that takes