<p>Your conjecture is correct. </p>

<p>If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from the mean subtraction which can be ignored from a complexity perspective).</p>

<p>Thus, covariance matrix computation is matrix multiplication which is naively indeed in $\mathcal{O}(Nn²)$ <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="nofollow noreferrer">see here</a>, since you have to do roughly $2N$ operations to fill every of the $n²$ positions in your covariance matrix $X$. In practice, matrix multiplication is speeded up to $\mathcal{O}(n^{2.73})$ for quadratic matrices (see the link).</p>

CC BY-SA 3.0
2018-02-10T10:46:03.690Z
2018-02-12T13:29:05.547Z
2018-02-12T13:29:05.547Z
dopexxx
<p>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.</p>

<p>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.</p>

<p>Is my assumption correct, or if not what is the asymptotic complexity?</p>

<time-complexity><linear-algebra><matrices>
What is computational complexity of calculating the Variance-Covariance Matrix?
Yet Another Geek
# What is computational complexity of calculating the Variance-Covariance Matrix?

(Asked by: username_0 on 2012-12-15)

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?

**Tags:** time-complexity, linear-algebra, matrices

---

## 1 answers

### Answer by username_1 on 2018-02-10. Score: 3 | Accepted answer

Your conjecture is correct.

If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from the mean subtraction which can be ignored from a complexity perspective).

Thus, covariance matrix computation is matrix multiplication which is naively indeed in $\mathcal{O}(Nn²)$ [see here](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations), since you have to do roughly $2N$ operations to fill every of the $n²$ positions in your covariance matrix $X$. In practice, matrix multiplication is speeded up to $\mathcal{O}(n^{2.73})$ for quadratic matrices (see the link).


---

