Union-Find & Analysis of Algorithms

• This case shows that, how to improve algorithm step by step.

Dynamic Connectivity

• Given a set of N objects.

• Union command: connect two objects.
• Find/connected query: is there a path connecting the two objects?
• We assume “is connected to” is an equivalence relation:

• Reflexive: p is connected to p.
• Symmetric: if p is connected to q, then q is connected to p.
• Transitive: if p is connected to q and q is connected to r, then p is connected to r.

First Solution: Connected components

• Maximal set of objects that are mutually connected.

Second Solution: Quick Find

• To merge components containing p and q, change all entries
whose id equals id[p] to id[q].

Final Solution: Weighted quick-union with path compression

• quick-union:

• weighted: Keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree.

• Keep the depth of any node x is at most lg N.
• path compression: Make every other node in path point to its grandparent.

• Code:

Analysis of Algorithms

Common Order-of-growth Classifications

• $1, \log{N}, N \log{N}, N^2, N^3, \text{ and } 2^N$
• * $\text{time} = \lg{T(N)}$ * $\text{size} = \lg{N}$

Why Big-Oh Notation

• Formal Definition: $T(n) = O(f(n))$ if and only if there exist constants $c,n_0 > 0$ such that $T(n) \le c \cdot f(n)$ for all $n \ge n_0$

• $T(n)$ is the function of the running time of an algorithm.
• Warning $c, n_0$ cannot depend on n.
• [NOTE] It kinds of says, we use $n^k$, but not $n^{k-1}$

• Because $O(n^{k-1}) = c \cdot n^{k-1}$ will always less then $n^k$ (c is a constant, but n is not).
• And we need that, T(n) is bounded above by a constant multiple of f(n).
• Example