What is the complexity of PageRanks Big-O?

Question

I am looking for the complexity of the PageRank algorithm for Big-O. I could hardly find anything, I just found O(n+m) ( n is the number of nodes, m is the number of arcs / edges), but so far I have not believed in this complexity.

I think there are no convergence criteria. I did not think that this is a constant, I think that convergence depends on the diameter of the graph. Enough to have Big-O for one iteration, then convergence is not important.

However, PageRank needs to touch each node and summarize each incoming rank, so I was expecting O(n * m) runtime.

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

Thanks in advance.

Answer 1

After some research and further thinking, I came to the conclusion that O(n+m) is the real thing.

Because even in the full schedule, you need to touch each edge twice. You can’t touch every edge, it was a mistake in my thoughts. Therefore, you have to touch at least each node, which is n times and twice each edge, which is m in large O. So, the correct answer is O(n+m)