Время работы алгоритма {{---}} <tex> O(E^2 \log U) </tex>.
|proof=
Пусть В ходе выполнения алгоритма масштаб <tex> \Delta </tex> принимает следующие значения: <tex> S = \{2^{\lfloor \log_2 U \rfloor}, \ldots, 2^k, \ldots, 2, 1, 0\} </tex> {{---}} множество масштабов. Тогда <tex> |S| = O(\log U) </tex> {{---}} количество итераций алгоритма.
{{Лемма
