Изменения

Оценка сложности остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общая сложность алгоритма — <tex> O(E^2 \log U) </tex>, q.e.d.