I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of Lanczos method.
Complexity analysis of Lanczos seems to be hard to find in the literature. Here are two leads, that might help a bit.
For the largest eigenvalue, you might find the complexity analysis in the following paper to be useful.
Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start by J. Kuczyński and H. Woźniakowski
A very important point raised in the above paper is that even if an eigenvalue is easily estimable, its corresponding eigenvector can be computationally hard to estimate!
Also see Lemma 2 of Fast algorithms for approximate semidefinite programming ... by S. Arora, E. Hazan, and S. Kale, for additional results.
Chapter 9 = Lanczos Methods, of "matrix computations", Golub, van Loan, John Hopkins univ press.