Изменения

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