CODEWITHSUNDEEP
algorithmtimebig-ocomplexity-theorytime-complexity
user3490561
user3490561

Reputation: 456

Algorithm Time Complexity Analysis (three nested for loops)

Here's the code I've implemented in a nutshell. The two inside for loop should have a complexity of O(n2) where n=vertices. I just can't figure out the overall time complexity along the outer for loop. I think its gonna be O( E * n2) where E is the number of edges and n is the number of vertices.

int vertices;

for(int Edges = 0; Edges < vertices-1 ; Edge++)
{
    for (int i=0; i< vertices; i++)
        for (int j=0; j<vertices; j++)
        {
            // TASKS
        } 
}

This code is for a prim algorithm. I can post the whole code if you want. Thanks :)

Upvotes: 0

Views: 595

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Sigma notation makes things clear:

enter image description here

Upvotes: 1

Am_I_Helpful
Am_I_Helpful

Reputation: 19178

Ahh!!! What is so typical about it!

In your inner loops,you have variables named i & j,so you figured out easily the complexity.

Just with an addition of EDGE variable which is not at all different from the other 2,you have got confused! Check the number of iterations!!!

The outer-loop would run VERTICES-1 iterations.

Therefore, complexity = (VERTICES-1) * (VERTICES) *(VERTICES) = (VERTICES^3) - (VERTICES^2).

Program's complexity would be O(Vertices^3) OR O(n^3) where n=vertices...

Upvotes: 2

Related Questions