How to calculate the complexity of this algorithm?

Asked

Viewed 707 times

-1

I would like an explanation of how to calculate the complexity of the algorithm below. I couldn’t understand very well 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.

PageRank

  • 4

    Possible duplicate of What is the complexity of an algorithm?

  • 1

    This is an algorithm distinct from the other questions. So there is no possible duplicate @Francisco

  • I ran the algorithm. The image helps to visualize each line better, so I chose to place it, since there are mathematical operations that can become complex to be viewed @diegofm

  • @diegofm I did not change the edit, I just put the pseudocode and left the image. Only this change I did

  • Got it, anyway, gets the hint when add code more than one line, use the {} that it formats better :)

  • 1

    The time complexity of the algorithm is how much it takes to process the instructions for a middle input, also has the best input and the worst entry. In this case, you need to weigh the weight of each operation (usually each small arithmetic operation has weight 1) and, if it has repetition, how many times it repeats. I will post a full reply later

  • 1

    Thanks @Jeffersonquesado. I’ll be waiting :)

Show 2 more comments

1 answer

1

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

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

This happens because the greatest nesting of ties is:

  • for each value in 1.. iteration
    • for each p in G
      • for each ip in the neighbors of p

Browser other questions tagged

You are not signed in. Login or sign up in order to post.