6.9. Amortized Complexity

So, formally the problem that we have claimed to solve is to maintain a partition of a set and update this partition, right. So, by partition we mean that we have a set s and it is broken up into some disjoint subsets. So, these subsets do not overlap, right and every element belongs to none of these things. So, there may be some which have more than one element and each element is assigned to exactly one partition, right and we call these partitions also components.

The Union-Find data structure is used to manage a collection of disjoint sets. This means that the sets do not overlap; each element is in one, and only one, set at any time. When we talk about 'partitioning', we refer to dividing a main set into smaller groups (or subsets) where each subset is unique. This becomes essential for certain algorithms, like Kruskal's for minimum spanning trees, where tracking which vertices belong to which component helps in avoiding cycles.

Imagine you have a group of friends, and you want to keep track of different circles of friendships. Each circle represents a partition of friends that does not overlap with other circles; if you have three friends in one circle, they do not share friends from another circle. The Union-Find structure helps to keep track of which 'circle' each friend belongs to.

So, we will call this a union-find data structure which supports these two operations efficiently, and the initialization of this union find is an operation which takes a set and breaks it up into n components each containing one element.

The Union-Find structure has two main operations: 'Find' and 'Union'. The 'Find' operation determines which component a particular element belongs to, while 'Union' merges two components into a single component. At the start, each element is its own component. This allows us to efficiently manage and update the relationships between elements in terms of their components.

Think of building blocks. Each individual block represents an element; when you have several blocks (that is, individual components), it’s easy to identify each one. If you group two blocks together, you perform a 'Union'. If you want to know which block is part of the group, you use 'Find'.

So, this will take order n time for just one union operation which is independent of the size of k and k prime as current partition sets.

In a basic implementation of union-find, performing the 'Union' operation can be very inefficient. When merging two components, you may have to check every element in the component, which takes linear time (order n). Thus, if you have multiple union operations, the total time could grow significantly – potentially up to quadratic time for a large number of elements.

Imagine trying to combine two large groups of friends at a party. If you need to ask every friend in both groups if they belong to the new merged group, it could take a long time, especially if the groups are large. This is similar to how a naive union operation can take too long because it checks every element.

The first thing as we said is updating a component is now proportional to its size, right. Up going updating component takes orders size of k is kept.

To improve efficiency, a smarter strategy relates to merging smaller components into larger ones - always keeping the larger set intact. This means when you union two components, you make the smaller one point to the larger one. This reduces the number of elements needing updating, making the 'Union' operation faster.

Consider a community organizing a fundraiser. If you have two smaller donor groups, rather than combining both groups completely, you merge the smaller group into the larger group. This way, you don't need to have all members of the smaller group re-introduced or checked against the larger group, reducing effort and time.

So, therefore, a component s can be relabeled a fixed, sorry a fixed element s can be relabeled at most log m times.

Amortized complexity refers to the average time taken per operation over a series of operations. Though certain operations may take a long time, by spreading the cost of infrequent, expensive operations across many cheaper operations, we find that the average is manageable. In the case of union-find, while merging operations may take longer at times, they are 'amortized' over all operations, leading to an efficient average time complexity.

Think of a gym membership. The initial fee (the 'setup cost') may be quite high, but as you continue using the gym, the average cost per visit decreases since you spread out that initial payment over all your visits throughout the year. This makes using the gym more affordable in the long run. Similarly, in amortized complexity, we assess the total cost of performing various operations and find an average cost per operation.

So, since that tree has only n minus 1 edge, we will only add n minus 1 edge out of the total set to find the spanning tree.

In algorithms such as Kruskal's for minimum spanning trees, the union-find structure is crucial. It allows efficient checking of whether two vertices belong to the same component and unites components when they don’t. The ability to perform these operations in almost constant time (on average) helps ensure the overall efficiency of the algorithm.

Imagine you're assembling a network of roads (edges) between towns (vertices). When you build a new road, you need to check if it connects two previously separate towns. The Union-Find structure lets you do this quickly, allowing you to decide which roads to build without repeating roads to the same town, similar to ensuring that towns are connected without forming unnecessary loops.

--