Изменения

Начальная сортировка и инициализация множеств <tex>L_r</tex> и <tex>I_r</tex> может быть произведена за <tex>O(N logN)</tex> времени. Время работы функции <tex>TreeSearch</tex> является суммой длительностей всех его вызовов. Каждый вызов от внешних узлов добавляет к этой сумме <tex>O(|L_v| + |Int_{a, b}(L_v)|)</tex>. Для внутренних же узлов, время требуемое для выполнения 10го шага алгоритма равно <tex>O(|I_v| log N)</tex>, а для остальных <tex>O(|S_v| + |Int(D_v, S_v')|)</tex>. Если мы все это сложим, то придем к выводу, что наш алгоритм работает за <tex>O(N log^2 N + K)</tex>. Заметим, что его скорость можно увеличить до <tex>O(N logN + K)</tex>, если не будем учитывать время нахождения <tex>Loc(D_v, s)</tex>.  Соответственно в оптимальном алгоритме Балабана <tex>Loc(D_v, s)</tex> находится за <tex>O(1)</tex>.