What's the complexity of Spearman's rank correlation coefficient computation?

Question

I've been studying the Spearman's rank correlation coefficient

$\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$.

for two lists $x_1, \dots, x_n$ and $y_1, \dots, y_n$. What's the complexity of the algorithm?

Since the algorithm should just compute $n$ subtractions, is it possible to be $O(n)$ ?

Answer 1

You have to compute

• two averages,
• $2n$ differences,
• three sums with $n$ summands -- which can be computed in constant time -- each and
• one division, one multiplication and one square root.

All of this can be done in linear time if we assume elementary arithmetic operations run in constant time, therefore total time in $O(n)$ is certainly possible. Note that computing the root might screw things up.

Regarding space, you have several options:

• Store only the averages, that is two numbers ($O(\log M)$ with $M$ the maximum number). You have to recompute all differences, that is perform a total of $6n$ subtractions.
• Store the average and the differences, that is $2n+2$ numbers ($O(n \cdot \log M)$). This saves you $4n$ subtractions.

Which is preferable depends on your context.

Answer 2

You have left out a important step... The formula you have is for the pearson correlation. What makes it spearman is that x and y are the ranks for the two original variables. This ranking step must be taken into account for the complexity of the spearman correlation coefficient. Essentially you must sort each of the two variables, which will depend on your chosen sorting algorithm, followed by the calculation mentioned above.