So the overall complexity for the computation of one term of C is hence O(r) where the value of r is directly connected to the magnitude λ of the second eigenvalue of the transition matrix.