What's the complexity of Spearman's rank correlation coefficient computation?
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.