171
правка
Изменения
Нет описания правки
<tex>T_g(n) \le T_g(n-1) + k_1 n^5 + k_2 n T_g(log_2 n)</tex>
Пусть <tex>T_g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
<tex>c (n-1)^6 7 + k_1 n^5 + 2 k_2 k_3 nc (log_2 n)^2 7 \le c n^67</tex>
Тогда, в силу <tex>T_g(1) = d \le c 1^67</tex> и неравенства выше, по индукции легко доказать, что <tex>T_g(n)</tex> ограничено сверху <tex>c n^67</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
== Источник ==
