Изменения
→Доказательство оценки времени выполнения
Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно за <tex>O(1)</tex>.
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. Операция init за <tex>O(n)</tex>, <tex>O(m)</tex> операций makeSet, findSet и часть работы операции union на обновление поля длины и слияния списков, каждая из которых выполняется за константное время и , а также суммарное время обновления указателей на представителя операцией union для каждого элемента.
}}
