We don't generally document the order of complexity of MATLAB functions, and for eigs we don't think it's possible to give a straight-up order of complexity. For eig, the complexity is O(n^3), but we cannot guarantee that eigs is within O(n^3).
The main problem is that eigs uses an iterative method, which is supposed to decrease the residual of the eigenvalues and eigenvectors in each step, until a tolerance tol is reached. So the computational complexity depends on the convergence speed of the method.
The straight-up Arnoldi method for computing the largest eigenvalues of A*x = lambda*x has a cost of O(n*p^2 + p^3) + p*[cost of A*x]. How large p needs to be depends on the convergence speed, which in turn depends on the relative gap between the eigenvalues. But this is typically prohibitively expensive because of the factor O(p^3) involved. In eigs, we use the "implicitly restarted Arnoldi" method as implemented in ARPACK, which uses several tricks that make the algorithm faster in the general case, but also make its convergence behavior and computational complexity much more difficult to analyze.
Additionally, if the smallest magnitude eigenvalues are requested, UMFPACK is used to factorize A, which is O(n^3) in the general case; you would need to know the sparsity structure of A to find any smaller bound.
If you want to investigate further, the following two papers are relevant:
[1] Lehoucq, R.B. and D.C. Sorensen, "Deflation Techniques for an Implicitly Re-Started Arnoldi Iteration," SIAM J. Matrix Analysis and Applications, Vol. 17, 1996, pp. 789–821.
[2] Sorensen, D.C., "Implicit Application of Polynomial Filters in a k-Step Arnoldi Method," SIAM J. Matrix Analysis and Applications, Vol. 13, 1992, pp. 357–385.
and there's also the ARPACK and UMFPACK documentations which should be available online.
