I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out from equations $Ax^{\*}=\lambda x^\*$ ($x^\*$ is exact solution) and $Ax^{(k+1)}=\lambda x^{(k)}$ and got this (if needed, I can write all steps):

$ ||x^{(k)} - x^\*|| \le {{log \left( {{\varepsilon} \over {C}} \right)} \over {log\ q}}$, where $C = {{\left|\left| x^{(0)} - x^{(1)} \right|\right|} \over {1-q}}$ and $q = \left|\left| {{A} \over {\lambda}} \right|\right| $.

It's awful. First, it depends on $x^{0}$ and $||A|| \sim O({m \over \sqrt{n}}) $. Second, it is not even upper bound. I've tried to google it, but found nothing specific. I'm sure better estimate exists.

Please, if you know something about that issue, share with me. Any help will be good: advices, possible way to solutions, articles, etc.

P.S. $A$ is sparce, n-by-n matrix with all non-negative real values. Number of positive elements is m.