The runtime and storage requirements you cite only apply when you need exact answers.

If you want to compute a correlation coefficient, you are probably happy to get eg 3 significant digits of precision. Thus you can use approximation algorithms and sampling.