LAPACK has following 4 routines for calculating eigenvalues of a real symmetric matrix; namely DSYEV, DSYEVD, DSYEVX and DSYEVR (DSYEVR being the recommended one).
If I were to calculate both eigenvalues and all the eigenvectors, how many floating point operations would each of the routine take. Are all these routines are based on tridiagonalization?
First of all, yes, these are all based on an initial tridiagonalization (often quoted to be $\frac{4}{3}n^3$ flops). DSYEV is just an easier to use version of DSYEVX, so let's ignore it for now. The basic breakdown is such:
The flop count of each of these algorithms is highly dependent on the eigenvalue distribution. For example, if your matrix has clusters of closely packed eigenvalues that are nearly degenerate, then these algorithms tend to have reduced order of convergence. At best you have $O(n^2)$ flops in the tridiagonal eigenproblem, and at worst $O(n^3)$ if the sizes of your clusters go as $O(n)$. See this working note for a more detailed analysis.
Since you want eigenvectors, let's look at the flop count for their extraction. Implicitly shifted QR continually updates the orthogonal matrices used for reduction, so it is always runs in $O(n^3)$ when eigenvectors are desired (basically, each QR bulge sweep takes $O(n^2)$, and you need to $O(n)$ sweeps usually).
For D&C and MRRR, the textbook descriptions say to compute eigenvalues first, then extract eigenvectors with inverse iteration. This requires $O(n)$ work per eigenvector since usually 1-2 iterations is enough, so it would be $O(n^2)$ work to get all the eigenvectors after the eigenvalues have been found. However, in practice, Lapack does something more sophisticated.
I'm not familiar with D&C, but look at the source, it looks like it keeps the eigenvectors updated as it goes, so it's runtime is likely somewhere between $O(n^2)$ and $O(n^3)$. For MRRR, the failure of inverse iteration has been analyzed in this paper. In practice, the eigenvectors must be updated throughout the algorithm and reorthogonalized when clusters are detected. A few of the details of this process can be controlled in the interface to DSYEVR, and like D&C, the practical runtime is somewhere between quadratic and cubic.
