1) For real symmetric (or complex Hermitian) eigenvalue problem, you can use xSYEVX (or xHEEVX) or xSYEVR (or xHEEVR) to compute only a few of the eigenvalues.
(So in particular for the largest one.) The cost of the algorithm will still be O(n^3) but this should be significantly faster than computing the whole spectrum.
2) For real nonsymetric (or complex nonHermitian) eigenvalue problem, LAPACK xGEEV subroutines compute all the eigenvalues.
3) Using software package based on iterative methods will reduce very likely the cost to O(n^2). (See for example ARPACK, BLOPEX, PRIMME.)