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