Ignoring eigenvectors, the shifted QR algorithm for computing eigenvalues in the symmetric tridiagional case costs $O(n)$ per iteration, converges globally, and converges cubically near the end. What is its worst case complexity (which presumably depends on the desired error)?
With the right shift stategy (mixing RQ and W shift appropriately), it is globally cubically convergent, with a guaranteed linear convergence factor, which makes its complexity of the order of $N$ times the logarithm of the off-diagonal entries. Unfortunately,
See http://www.springerlink.com/content/f1w76x84463l52t7/ for local cubic convergence.