  In an extension of Kendall's $\tau$, Bergsma and Dassios (2014) introduced a
covariance measure $\tau^*$ for two ordinal random variables that vanishes if
and only if the two variables are independent. For a sample of size $n$, a
direct computation of $t^*$, the empirical version of $\tau^*$, requires
$O(n^4)$ operations. We derive an algorithm that computes the statistic using
only $O(n^2\log(n))$ operations.

Computation