Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same
If the matrix has two distinct eigenvalues, you can find them using power iteration.

Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| &gt; |\lambda_2|$.  Then you can use power iteration to find $\lambda_1$.  Next, set $A' = A - \lambda_1 \text{Id}$.  $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ reveals $\lambda_2$.

The running time depends on the exact values of $\lambda_1,\lambda_2$; power iteration converges geometrically with ratio $|\lambda_2|/|\lambda_1$, so if $|\lambda_2$ is sufficiently smaller than $|\lambda_1$, you can obtain a very precise estimate with a fairly small number of iterations; if they are very close, power iteration will be ineffective.

I don't know how to generalize this handle a matrix with three distinct eigenvalues.