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