Kruskal algorithm time complexity | Time complexity of Kruskal algorithm

The Kruskal algorithm is a famous greedy algorithm. Like other algorithm coding implementations, the Kruskal algorithm implementation does not affect so much on the time complexity. Firstly we have to know the basics of the Kruskal algorithm. The basics said that we have to select an edge with minimum cost or weight. Then see the two vertex head area from the selected minimum weight edge. If the edges with minimum weight are already in a tree then don't take this or count this for the finding of the minimum spanning tree. Then traverse in another vertex and continue the process until we go to the destination point. 

The time complexity of the Kruskal algorithm is divided into two parts. The first part is sorting the edges and the loop will run for the n-length edges. The second part is to find the vertex to count with the result or not for the minimum cost path. We will consider the below graph for this problem.

kruskal

Fig. 01: figure for the krushkal algorithm

n = sum of all edges in the graph

n = ( AB + BC + ..... + DE )

m = m length vertex

m = ( A + B + .... + E)

Time complexity for sorting edges and n-length loop

As we know that in a sorting algorithm the time complexity is simply O(n*n). Because there will be two loops with n-length for the comparison between elements. So, the time complexity for the sorting section is O(n*n). But, we can reduce the O(n*n) to the log n complexity using the library sort function. As we will push the m-length vertex, the time complexity will be log m. Code will be like this in c++, 

vector <Edge> E;

sort(E.begin(), E.end());

Then, for running a simple loop for the n-length size, the time complexity is O(n). As we are considering the m-length vertex, the time complexity for m-length loop is O(m). 

for (int i=0; i<m.size(); i++)

{

}

Then, the overall time complexity of this section is, 

Time complexity = O (m) * O (log m)

= O ( m log m)

Time complexity for finding the vertex

In any language, for finding an element-time complexity is O (1). Because there is no n-length loop will run. For the m-length size O(1)  = O(m)

The implementation will be like the below in the c++, 

int find(int el)

{

if (f[el] == el) return el;

return f[el] = find (f[el]);

}

if ( find(E[i].u) != find(E[i].v) )

{

}


Final Time Complexity 

Now the final time complexity is, 

Time complexity = O (m log m) + O(m)

= O (m log m + m)

= O (m log m)

So, the time complexity of the Kruskal algorithm is O (m log m).

Read Similar Posts:

1. BFS Time Complexity

2. Quick Sort Time Complexity

3. Insertion Sort Time Complexity

4. Merge Sort Time Complexity

5. Linear Programming Time Reduction

6. Dijkstra Algorithm Time Complexity

7. Bellman For Algorithm Time Complexity

8. DFS Time Complexity


Post a Comment

Previous Post Next Post