Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector decomposition is causing the largest performance hit, I am wondering how much of that hit is caused by the Covariance Matrix computation.

The asymptotic running time I estimate it to use is $O(N\cdot n^2)$ using a naive algorithm, because it has to take the means of all the data of size $N$ and then has to do it for every dimension (where $n$ is the number of dimensions) in a nested iteration, and thus producing a $n^2$ size matrix.

Is my assumption correct, or if not what is the asymptotic complexity?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.