The standard way of adjusting mutual information against chance is through random label permutations of one of the clusterings [1]}. Unfortunately, this adjustment makes the metric computationally expensive. Specifically, the time complexity of the metric is in \(O(\max (k,l)n)\) , where \(k, l\)  are the numbers of clusters in each clustering and \(n\)  is the number of samples [2]}. As a comparison, the time complexity of mutual information is equal to
\(O(kl)\)  given the contingency matrix of the clusterings, i.e., the matrix counting the number of samples in each cluster pair.
The additional computational effort required by adjustment is significant as the number of samples \(n\)  is typically much larger than the numbers of clusters \(k,l\) .
