Efficient Computation of the Bergsma-Dassios Sign Covariance

In an extension of Kendalls $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^2log(n))$ operations.