Изменения
Нет описания правки
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le leqslant N'\le leqslant N</tex>,
Докажем:
: <tex>T(M,N) \le leqslant 2MN</tex>
База индукции очевидна
: <tex>T(1,N) = N \le leqslant 2N</tex>Пусть для всех <tex>M' < M</tex> выполнено <tex>T(M',N') \le leqslant 2M'N'</tex>. Тогда учитывая <tex>T(M/2,N') \le leqslant 2(M/2)N'</tex>, <tex>T(M/2,N-N') \le leqslant 2(M/2)(N-N')</tex>, получим:: <tex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \leleqslant</tex> <tex> MN+2(M/2)N'+2(M/2)(N-N')=2MN</tex>
следовательно
: <tex>T(M,N) = \Theta(M \cdot N)</tex>
