What is the computational complexity for diagonalizing covariance matrix

Question

I am considering using an algorithm called Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for global optimization. Part of the algorithm involves taking a square root of a covariance matrix, which requires that the matrix be diagonalized. Since the covariance matrix will be rather large $(N\ge100)$ I am concerned about the computational cost of this square root step. What is the computational complexity for diagonalizing a covariance matrix? Or is there anyway of computing the square root of a matrix without diagonalizing?

Answer 1

Probably you should take realization of Singular Value Decomposition algorithm, it's complexity is $O(N^3)$.