Изменения

Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1первой лемме]]). [[#l2|По Лемме 2второй лемме]] алгоритм делает не более <tex>2n</tex> явных продлений. Таким образом, в течение всех <tex>n</tex> итерация суммарно выполняется не более <tex>O(n)</tex> продлений, следовательно, с использованием всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.