Изменения
→Время работы
<tex>\forall v \in V \ |S_v'| \le a_v - b_v + |Int(D_v, S_v')|</tex>.
|proof=
Утверждение напрямую вытекает из [[#lemma1|первой леммы]] (далее лемма №1) и очевидного факта, что для любого множества <tex>S \subset S_0</tex>, количество концов отрезков, лежащих в полосе <tex>\langle a_v, b_v \rangle</tex>, меньше чем <tex>b_v - a_v</tex>.
}}
Утверждение напрямую вытекает из [[#lemma2|леммы №2]] и следующего отношения <tex>\sum_v (b_v - a_v) \le 2N \lceil logN + 1 \rceil</tex>.
}}
Обозначим множество всех вершин рекурсивного дерева за <tex>RT</tex>.
{{Теорема
<tex>\sum_{v \in RT} |S_v| \le N \lceil 4logN + 5 \rceil + 2K</tex>
|proof=
Для всех узлов, кроме корня <tex>r</tex> имеет место выражение <tex>|S_v| \le |S_{ft(v)}'|</tex>, следовательно <tex>\sum_{v \in RT} |S_v| \le |S_r| + \sum_{v \in RT \setminus r} |S_{ft(v)}| \le N + 2 \sum_{v \in V} |s_vS_v'| \le N \lceil 4 logN + 5 \rceil + 2K</tex>.
}}
Начальная сортировка и инициализация множеств <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>Loc(D_v, s)</tex> равно <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>.
