Изменения

Рассмотрим произвольный элемент <tex>memo[i]</tex>. Заметим, что условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex> не более одного раза. Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>r(n)</tex> раз. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>r(n)</tex> раз, а значит в дереве не более <tex>r(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot r(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.

}}