# complexity of on-line correlation

I am computing pairwise correlation between the N rows of a matrix $$X_{(N,G)}$$ using two methods.

1- Direct computation

Zx is the z-scored X along the columns

$$C_n=\frac{Zx'*Zx}{(N-1)}$$

2- On-line computation

In this case, we assume that we know the correlation (and the covariance) of the N-1 rows and we would like to compute the new correlation using a new observation $$x_n$$.

To compute the correlation on-line between two vectors X and Y, I used the following formula:

$$COV_{n}(X,Y)=\frac{COV_{n-1}(X,Y).(N-1)+\frac{N}{N-1}(x-\bar{x_n})(y-\bar{y_n})}{N}$$

then

$$C_n=\frac{COV_{n}}{\sigma_{x,n}\sigma_{y,n}}$$

The standard deviation is computed on-line using this formula:

$$\sigma_n^2=\frac{n-2}{n-1}\sigma^2_{n-1}+\frac{1}{n}(X_n-\bar{X_{n-1}})^2$$

Where we also use the computation of the mean on-line

$$\bar X_n = n^{-1}[X_n + (n-1)\bar X_{n-1}]$$

My question is when does it become interesting (in memory usage and/or speedup) to use on-line versus direct (there is only one step in on-line method)?

The first approach is in $$O(G*N^2)$$ but I could not figure out the complexity of the second approach.