Content deleted Content added
→Making new sets: Add an explanation for the pseudo code conditional. Could apply to a node intrusive field as the examples or a separate dictionary of node-to-parents. |
|||
Line 197:
=== Proof of O(m log* n) time complexity of Union-Find ===
The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any {{mvar|m}} <code>Find</code> or <code>Union</code> operations on a disjoint-set forest containing {{mvar|n}} objects is {{math|''O''(
{{anchor|increasing rank lemma}}Lemma 1: As the [[#Disjoint-set forests|find function]] follows the path along to the root, the rank of node it encounters is increasing.
| |||