I have read that the computational cost of full eigendecomposition (finding both eigenvalues and eigenvectors) is $O(n^3)$. But what is the cost if we want to find only eigenvalues?
How does MATLAB function eig work? Does the time depend on whether you ask only for the eigenvalues or also for the eigenvectors?
Clearly, we search approximations of eigen-values (-vectors) with a fixed number of significand digits. In these conditions, we assume that our real matrix $A$ is diagonalizable over $\mathbb{C}$ by a change of basis of matrix $P$.
The complexities are $\approx 15n^3$ for the eigenvalues and $\approx 40n^3$ for values-vectors. Of course, the direct calculation is not stable when the condition number of $P$ is bad. Thus, in general, the standard algorithm uses a small number of iterations (2 or 3 in general for each eigenvalue).
Of course, when the matrix is symmetric, there is no problem with $P$ and the algorithm is in general stable. We can divide the above complexities by 2 for these matrices.