How to determine the time complexity of an algorithm depending on a delta value

user_4839846 0
Viewed 453

I have to study PageRank right now, and I have written this algorithm :

Algorithm

I have determined the complexity of the inside of the while loop, which I believe to be O(n^2). But then I'm stuck with the complexity of the while loop itself, which is inherently determined by delta. Delta being the difference of the L1 norm of R at the iteration i and R at the iteration i+1.

Is there any method for determining such a complexity ?

EDIT : a bit more explanation :

  • R is the rank vector
  • epsilon is a value given by the user (we want epsilon to be small to have a good estimate of PageRank but not too small it takes ages to compute it)
  • creerMatricePageRank() cretes the adjacency matrix for us, complete with the rank source vector E added in the mix
  • A is the adjacency matrix
pagerank time-complexity algorithm
1 Answers

The innermost for goes from 0 to t, which means O(t). The outer for goes from 0 to t, which means O(t) * O(t) = O(t^2).

Then you have another for which does nothing in O(t) time. It does nothing because it first computes d2 and the statement right after it assigns the value of d1 to d2 (both are equal delta now). The next statement delta = |d1 - d2| is saying delta = |delta - delta| == delta = 0.

If epsilon is negative, then the while loop never ends, otherwise the loop ends after one iteration, which means O(t^2) complexity.

Something is obviously wrong with your code. You either don't need that while loop at all or you mixed up the assignments.

user_67494810
Related