Efficient computation of the Bergsma–Dassios sign covariance

In an extension of Kendall’s $$\tau $$ τ , Bergsma and Dassios (Bernoulli 20(2):1006–1028, 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^*$$ t ∗ , the empirical version of $$\tau ^*$$ τ ∗ , requires $$O(n^4)$$ O ( n 4 ) operations. We derive an algorithm that computes the statistic using only $$O \left( n^2\log (n)\right) $$ O n 2 log ( n ) operations.