Изменения
Нет описания правки
Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>.
При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг вершины по условию возрастает до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,
необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.
Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>.
