Изменения

|proof = [[Файл:ve2.png|thumb|600px|Оценка количества переподвешиваний]] Вычислим верхнюю границу количества обновлений указателя Оценим время работы необходимое для обновления указателей на представителя в операциях union. Оценим количество обновлений отдельно для каждого элемента. Оказывается, что для каждого элементамы можем обновить указатель не более <tex>O(\log n)</tex> раз. Рассмотрим некий фиксированный Это связано с тем, что при каждом объединении множество в котором оказывается объектувеличивается не менее чем вдвое. Когда Действительно, так как мы обновляем указатель на представителя в элементеэлементу, он должен находиться то этот элемент находился в меньшем из множеств(согласно нашей эвристике), но тогда размер второго множества не меньше. Следовательно, при первом обновлении образованное множество хранит Тогда после первого обновления элемент содержится в множестве в котором не менее 2 двух элементов, при втором не менее 4 элементовпосле второго - четырех, и ттак далее.д. Продолжая рассуждение приходим к выводу о томВ силу того, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не содержать более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен количество обновлений не более превосходит <tex>\left\lceil O(\log n \right\rceil)</tex> раз.  Таким образом, общее время, необходимое для обновления указателей для n объектовэлементов, составляет <tex>O(n \log n)</tex>.

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