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