What is computational complexity of calculating the Variance-Covariance Matrix? 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?
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, 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).