Изменения

|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из <tex>n</tex> элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множестав. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Таким образом, при <tex>k \leqslant\ n</tex>, после того как указатель на представителя в объекте обновлен <tex>\left\lceil lg \ k \right\rceil</tex>, полученное в результате множество должно иметь не менее <tex>k</tex> элементов. Но максимальное множество может иметь не более <tex>n</tex> элементов. Значит указатель на каждом объекте поменяется не более }}