Big O of an algorithm that relies on convergence
Usually we prove something about the rate of convergence.  For instance, we might prove that after $k$ iterations, the relative error is $1/2^k$.  Thus if each iteration takes (say) $O(n^2)$ time, and we want an answer that has relative error at most $\epsilon$, then we have found an algorithm whose running time is $O(n^2 \lg (1/\epsilon))$.  Notice how the running time now depends both on the input size and on the desired accuracy of the answer.

For instance, PageRank uses power iteration.  As you can see from the Wikipedia page on power iteration, it is possible to prove results about its rate of convergence (as a function of the first two largest eigenvalues $\lambda_1,\lambda_2$).