76
правок
Изменения
Нет описания правки
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max\max(T(q)+T(n-q-1))+\Theta(n)</tex>,где <tex>0 \leq q \leq n-1</tex>,
так как мы разбиваемся на 2 подзадачи.
Предположим, что <tex>T(n) \leq c(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max\max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>
