disjoint dynamic equivalence
> For the find operation to be fast, we could maintain, in an array, the
> name of the equivalence class for each element. Then find is just a
> simple O(1) lookup. Suppose we want to perform union(a, b). Suppose
> that a is in equivalence class i and b is in equivalence class j. Then
> we scan down the array, changing all i's to j. Unfortunately, this
> scan takes (n). Thus, a sequence of n - 1 unions (the maximum, since
> then everything is in one set), would take O(n square) time. If there
> are (n square) find operations, this performance is fine, since the
> total running time would then amount to O(1) for each union or find
> operation over the course of the algorithm. If there are fewer finds,
> this bound is not acceptable.
> 
> One idea is to keep all the elements that are in the same equivalence
> class in a linked list. This saves time when updating, because we do
> not have to search through the entire array. This by itself does not
> reduce the asymptotic running time, because it is still possible to
> perform (n square) equivalence class updates over the course of the
> algorithm.
> 
> If we also keep track of the size of each equivalence class, and when
> performing unions we change the name of the smaller equivalence class
> to the larger, then the total time spent for (n - 1) merges is O (n
> log n). The reason for this is that each element can have its
> equivalence class changed at most log n times, since every time its
> class is changed, its new equivalence class is at least twice as large
> as its old. Using this strategy, any sequence of m finds and up to n -
> 1 unions takes at most O(m + n log n) time.

I have following questions on above notes. can any one pls explain

1. In first paragraph what does author mean by "total running time would then amount to 
O(1) for each union or find operation over the course of the algorithm" ?
2. In last paragraph how author came with "each element can have its equivalence class changed at most log n times" ?
3. In last paragraph how new equivalence class is at least twice as large as its old?

Thanks!


disjoint dynamic equivalence
===

> For the find operation to be fast, we could maintain, in an array, the
> name of the equivalence class for each element. Then find is just a
> simple O(1) lookup. Suppose we want to perform union(a, b). Suppose
> that a is in equivalence class i and b is in equivalence class j. Then
> we scan down the array, changing all i's to j. Unfortunately, this
> scan takes (n). Thus, a sequence of n - 1 unions (the maximum, since
> then everything is in one set), would take O(n square) time. If there
> are (n square) find operations, this performance is fine, since the
> total running time would then amount to O(1) for each union or find
> operation over the course of the algorithm. If there are fewer finds,
> this bound is not acceptable.
> 
> One idea is to keep all the elements that are in the same equivalence
> class in a linked list. This saves time when updating, because we do
> not have to search through the entire array. This by itself does not
> reduce the asymptotic running time, because it is still possible to
> perform (n square) equivalence class updates over the course of the
> algorithm.
> 
> If we also keep track of the size of each equivalence class, and when
> performing unions we change the name of the smaller equivalence class
> to the larger, then the total time spent for (n - 1) merges is O (n
> log n). The reason for this is that each element can have its
> equivalence class changed at most log n times, since every time its
> class is changed, its new equivalence class is at least twice as large
> as its old. Using this strategy, any sequence of m finds and up to n -
> 1 unions takes at most O(m + n log n) time.

I have following questions on above notes. can any one pls explain

1. In first paragraph what does author mean by "total running time would then amount to 
O(1) for each union or find operation over the course of the algorithm" ?
2. In last paragraph how author came with "each element can have its equivalence class changed at most log n times" ?
3. In last paragraph how new equivalence class is at least twice as large as its old?

Thanks!

