**Homework Help: Questions and Answers:** Suppose we implement a three-based union-find data structure, but we don’t use the union by-size heuristic nor the path-compression heuristic. Show that the total running time for performing a sequence of n union and find operations, starting with n singleton sets, is Θ(n^2) in this case. That is, provide a proof that it is O(n^2) and an example that requires Ω(n^2) time.

**Answer:**

Let’s start with analyzing the time complexity of a union-find (or disjoint-set) data structure when two common heuristics, **union by size** and **path compression**, are *not* used. We aim to show that the total running time for performing a sequence of n `union`

and `find`

operations, starting with n singleton sets, is Θ(n2). Specifically, we need to show both the upper bound O(n2) and lower bound Ω(n2) to establish that the running time is Θ(n2).

**Union-Find without Heuristics**

The operations we are considering are:

**Find(x):**Determines the root (or representative) of the set containing element x.**Union(x, y):**Merges the sets containing elements x and y.

Without using union by size and path compression:

**Union:**Each union simply makes one root point to another root without considering the size of the sets.**Find:**Traversing the tree from an element to its root involves going up the tree, potentially to the highest ancestor.

Without these optimizations, the structure of the trees formed can be quite inefficient, which leads to the performance degradation we’re investigating.

**Upper Bound: O(n2)**

Let’s begin by proving the upper bound.

**Step 1: Representation**

Initially, we have n singleton sets, i.e., each element forms its own set and is its own root. When a `union(x, y)`

operation is performed, we connect the root of one set to the root of another. If no specific strategy is used (like union by size or path compression), the resulting trees can become imbalanced.

**Step 2: Worst-case Find Operation**

In the worst-case scenario, each union operation results in increasingly taller trees, because we could always make one root the child of another. If we repeatedly perform `union`

operations in a way that causes one tree to be a long chain, a `find`

operation on the deepest node will take O(n) time.

For example, after performing n−1 union operations, the trees can form a single linear structure (i.e., a chain). In such a chain, the worst-case time for a `find`

operation on the last element is proportional to the number of elements in the chain, which could be up to n−1.

**Step 3: Total Cost of All Operations**

Since each `find`

operation in the worst case can take O(n) time, and there are n elements on which we perform both union and find operations, the total cost of performing n `union`

and `find`

operations can be bounded by:

O(n) (cost of a single find in the worst case) × O(n) (number of operations) = O(n2)

Thus, the overall running time is O(n2).

**Lower Bound: Ω(n2)**

Now, we will demonstrate a specific case where the time complexity is Ω(n2), establishing the lower bound.

**Step 1: Worst-Case Union Sequence**

We can perform a sequence of union operations that results in the most unbalanced trees possible. For example, consider a series of unions where each new element is unioned with the previously formed set in such a way that the tree becomes a long, skewed chain:

- Union(1, 2) results in 1 being the parent of 2.
- Union(2, 3) results in 1 being the parent of 2 and 2 being the parent of 3.
- Union(3, 4) results in 1 being the parent of 2, 2 being the parent of 3, and 3 being the parent of 4.
- Continuing this pattern…

After n−1 union operations, we will have a tree that is essentially a chain of n elements.

**Step 2: Find Cost**

Now, consider performing a `find`

operation on the deepest element (which is the last element added to the chain). To find the root of this element, we need to traverse through n−1 nodes. Thus, the time for a `find`

operation on this element is O(n).

**Step 3: Total Time for Sequence**

If we perform `find`

operations repeatedly on all elements after constructing this chain through n−1 unions, the total cost is as follows:

- The first find operation takes 1 step (for the root element).
- The second find operation takes 2 steps (for the second element in the chain).
- The third find operation takes 3 steps, and so on, up to the nth element, which takes n steps.

Thus, the total time for performing these `find`

operations is:

1+2+3+⋯+(n−1)+n=n(n+1)/2 = Ω(n2)

This shows that in the worst case, the time complexity for performing n union and find operations is Ω(n2).

**Conclusion**

Since we have shown both the upper bound O(n2) and the lower bound Ω(n2), we can conclude that the total running time for performing n union and find operations, without using union by size or path compression, is Θ(n2).

**Learn More:** **Homework Help**

Q. Processor execution time can be reduced by which of the following?

Q. Why would a user want to compress a large file before sending it as an email attachment?