Content deleted Content added
m Disambiguating links to Coq (link changed to Coq (software)) using DisamAssist. |
→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 58:
disjoint-set forest with {{mvar|n}} nodes requires {{math|''O''(''n'')}}
time.
Lack of a parent assigned to the node implies that the node is not present in the forest.
In practice, <code>MakeSet</code> must be preceded by an operation that allocates memory to hold {{math|x}}. As long as memory allocation is an amortized constant-time operation, as it is for a good [[dynamic array]] implementation, it does not change the asymptotic performance of the random-set forest.
| |||