Efficient computation of the Bergsma-Dassios sign covariance

In an extension of Kendall's , Bergsma and Dassios (Bernoulli 20(2):1006-1028, 2014) introduced a covariance measure 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 , the empirical version of , requires operations. We derive an algorithm that computes the statistic using only operations.