Convergence of QR method How does the number of iterations for QR-method for eigenvalues to converge depend on the matrix size $n$? 
I ran a MATLAB code for $n$ from 10 to 400 and the number of iterations before convergence does increase, but I can't seem to find any analytical approximations of such growth rate.
 A: For a Hermitian or symmetric matrix, the time to compute the eigenvalues is dominated by time to reduce the matrix to tridiagonal form: approximately $4n^3/3$ floating point operations.
Since the convergence of shifted QR is at least quadratic (and usually cubic), each eigenvalue can be computed to machine precision in a number of iterations of the QR decomposition independent of $n.$  So the number of iterations is $O(n)$ (a constant number times the number of eigenvalues). This answers your question for the Hermitian case.
Since a QR decomposition of a tridiagonal matrix can be computed in $O(n)$ floating point operations, the total time for computing eigenvalues after reducing to tridiagonal form is $O(n^2)$ floating point operations.  
See "Numerical Linear Algebra" by Trefethen and Bau for details.
For a non-symmetric matrix, Francis's double-shift algorithm is used on a reduction of the matrix to upper Hessenberg form.    The convergence rate of the double-shift algorithm is usually quadratic, so the number of iterations will still be a constant times the number of eigenvalues (in other words, $O(n)$).  However, since the QR decomposition of an upper Hessenberg matrix takes approximately $6n^2$ operations, more time will be spent on the iterative part of the algorithm than on the reduction to Hessenberg form.  See David S. Watkins's paper on Francis's algorithm for details.
