Изменения

Амортизированная стоимость<tex> S= {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v : \in get,v \in T3} \limits 1} ) / m </tex> , где <tex> {v \in get } </tex> означает что ребро начало которого находится в <tex> v </tex> было пройдено во время выполнения текущего <tex> get </tex>.

В силу того что <tex>{\sum_{v:v \in get,v \in T1} \limits 1} = O(1) </tex> получаем <tex> S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/m </tex> .

После Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второй леммы второго утверждения получаем что <tex> {\sum_{v:v \in get,v \in T2} \limits} = \le log^*_x(log_2(n)) = O(log^*(n)) </tex> . Для того чтоб <tex> log^*_x </tex> существовал необходимо чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>

Рассмотрим сумму <tex>{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1~/m < {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/n </tex> Из первого утверждения следует <tex> R(P(x)) </tex> только cтрого увеличивается при переходе по ребру из Т3.

<tex> {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T3} \limits } 1/n < \le \sum_v \limits x^{R(v)} /n < /tex>.  Из второго следствия второго утверждение следует <tex> {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n \le \sum_{Rank=0}^{log_{2}(n)} \limits {nx^{Rank} \over n 2^{Rank}} </tex>.При <tex> x < 2~~~{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n < { 2 \over 2-x } = = O(1) </tex>. В результате <tex> S=O(1)+O(1log^*(x))+O(1)=O(1log^*(x)) </tex>.