What is PageRanks Big-O complexity?

Question

I'm searching for the Big-O complexity of PageRank algorithm. I hardly could found anything, I just found O(n+m) ( n - number of nodes, m - number of arcs/edges) but I didn't believe this complexity by now.

I think it is missing the convergence criteria. I didn't think that this is a constant, I think the convergence depends on the graph diameter. It might be enough to have the Big-O for one iteration, then convergence is not important.

Nevertheless PageRank need to touch every node and aggregate every incoming rank, so I expected a runtime of O(n * m).

Did I miss something? Did anyone know a valuable source for the Big-O complexity of PageRank?

Thanks in advance.

Answer 1

After some research and further thinking I have come to the conclusion that O(n+m) ist the real thing.

Because even in a complete graph, one has to touch each edge twice. One could not touch every edge, that was the mistake in my thinkings. Therefor one has to touch at least every node, which is n times and two times each edge which is m in big O. So the correct answer is O(n+m)