How to calculate the complexity of this algorithm?

0

I would like an explanation of how to calculate the complexity of the algorithm below. I could not quite understand it by using graph theory.

FUNCTION PageRank (G, iterarion)
    d = 0.85
    oh = G
    ih = G
    N = G
    for all p in the graph do
        opg[p] = 1 / N
    end for
    while iteration > 0 do
        dp = 0
        for all p that has no out-links do
            dp = dp + d * (opg[p] / N)
        end for
        for all p in the graph G do
            npg[p] = dp + ((1-d)/N)
            for all ip int ih[p] do
                npg[p] = npg[p] + ((d*opg[ip])/oh[ip])
            end for
        end for
        opg = npg
        iteration = iteration - 1
    end while
end function

The image below helps to better visualize the algorithm with its respective lines.

    
asked by anonymous 12.06.2017 / 14:37

1 answer

0

This algorithm is O(i * n^2) considering the worst case (a complete graph ), where:

  • n is the number of nodes in the graph
  • ì is the value of the variable iteration

This happens because the biggest loop nesting is:

  • for each value in 1..iteration
    • for each p in G
      • for each ip in the neighbors of p
05.11.2018 / 12:17