Computing the distribution of spearman's footrule in O ( n^4 ) time

Consider the exact distribution of Spearman's "footrule", D(\sigma, \pi) = \sum_{i=1}^n \vert \sigma (i) - \pi (i)\vert , where \sigma and \pi are chosen independently at random from S_n , the set of all permutations of the first n integers; or, equivalently, where \sigma is chosen at random and \pi = (1,2,\ldots,n) . This can obviously be obtained by complete enumeration of all n ! permutations: that is, in O(n!) time. However, we show that the intrinsically different approach used by Salama and Quade (1990) reduces the computation to the polynomial-time class, specifically, to O(n^4) time.

Keywords:

• Spearman's Footrule
• Complete Enumeration
• Polynomial-time Calculation
• Permutations