Изменения

+

{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m

</center>

где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.

<tex>

S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m

</center>

<center>

<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))

</center>

<

{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n

Из первого утверждения и в силу использования сжатия путей следует,

что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.

{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }

1/n \le \sum_v \limits x^{R(v)} /n

Из второго следствия второго утверждения следует

<center> <tex>

{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}

При <tex> x < 2~</tex>:

\le

{ 2 \over 2-x } = O(1)