5.5. Complexity Analysis

The first step in Kruskal's algorithms requires sorting the edges. Sorting can be done in O(m log m) time, where m is the number of edges. Since n is at most n squared, log n will be roughly 2 times log n, which means O(log n) is the same as O(log m). Thus, the sorting step takes O(m log m) time.

The initial phase of Kruskal's algorithm involves sorting all the edges of the graph by their weights. This means we take all the edges and arrange them in ascending order based on how heavy or light they are. The sorting operation itself is a crucial step because it dictates how we process the edges in the algorithm. The time it takes to sort is expressed as O(m log m), which is a common time complexity for sorting algorithms. Here, m refers to the number of edges. In terms of the number of vertices n, we can relate the edges to the vertices since every edge connects two vertices, which gives us the maximum of m to be proportional to n squared. So, sorting is a necessary first step that sets up our algorithm for the next phases.

Think of sorting the edges as organizing a stack of papers by weight before you start selecting which papers to include in a project. If you can see the paper's weight, you can make quick decisions about which paper to use first based on what's lightweight (or less costly) before making a heavier choice, just like picking the lightest edges in the algorithm.

We have an outer loop that runs through all the edges in the list. The loop runs m times, and each time we update the components of the graph. This update happens n - 1 times, leading to a complexity of O(n^2). Each update requires a linear scan of all vertices to adjust component labels accordingly.

Once we have the edges sorted, Kruskal's algorithm enters a loop where it examines each edge one by one. This outer loop runs m times, which is the total number of edges. For each edge examined, the algorithm checks if adding that edge would create a cycle in the spanning tree being formed. If it does not create a cycle, the edge is added, and we must then update the components of the graph to reflect that these two vertices are now connected. This updating requires us to go through potentially all vertices in the graph (linear time), and since we are doing this for every edge added, this adds up to n - 1 times. Therefore, the combination of the outer loop and updates results in a complexity of O(n^2).

Imagine you're trying to group students into teams based on their strengths. You have a list of how each student can interact with others (edges) and you’re checking each student pair systematically. If you pick a student pair (edge) that works well together (doesn't result in conflict), you then have to update your team list (components) to show they’re now on the same team. This repetitive checking and updating, just like edge addition, can become cumbersome if there are many students (vertices).

To optimize our component merging process, we can use a data structure known as 'union-find'. This efficiently handles the component connections and reduces the complexity from O(n^2) to nearly O(m log n) for maintaining components.

The inefficiency noted in earlier steps primarily arises from the need to repeatedly check and update component labels through linear scans. This is where the union-find data structure becomes valuable. Using union-find, we can quickly determine the component of any vertex and merge them when necessary. The union operation connects two disjoint sets, while the find operation retrieves the component label for any vertex. This combination allows us to manage the connections efficiently, leading to significantly reduced complexity in handling components during the algorithm's execution.

Consider a phone directory where every person is initially listed as separate. Instead of looking through names (vertices) one by one to see who belongs to which group (component), imagine a system that instantly tells you everyone in your phone contact group (union-find). So, if someone new joins your group, you can easily merge their information with the rest without having to look through the entire list, making your life much simpler and faster.

--