How expensive is it to compute the eigenvalues of a matrix? 

What is the complexity of the best algorithms? 

How long might it take in practice if I have a 1000 x 1000 matrix? I assume it helps if the matrix is sparse?

Are there any cases where the eigenvalue computation would not terminate? 

In `R`, I can compute the eigenvalues as in the following toy example:

```
m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14  3

```

Does anyone know what algorithm it uses? 

Are there any other (open-source) packages that compute the eigenvalue?